문제 설명

Given the head of a linked list, rotate the list to the right by k places.

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

풀이

• rotate를 1번 할 때마다 head가 바뀜

• 0 -> n-1 -> n-2 -> n-3 ... -> 0

• dic에 초기 idx 정보를 저장

• 리스트의 길이가 n일 때

• rotate한 횟수 = k

• head = n-k

• 마지막 node와 head를 연결 -> circular 리스트임

• head가 될 node는 n-k

• tail은 head가 될 node idx 하나 전임

• tail의 next = None

  결과적으로 Listnode를 한 번 순회하므로 O(N)
  ps.근데 성능이 제출할 때마다 매번 오락가락인데 왜일까..

  

  class Solution:
     def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
         if head == None: return head
  
         #head가 될 node는 n-k
         #tail은 head가 될 node idx 하나 전임
         #tail의 next = None
         dic = {}
         node = head
         idx = 0
         bf = None
  
         while node:
             dic[idx] = node
             bf = node
             node = node.next
             idx += 1
  
         k = k % len(dic)
         if k == 0: return head
  
         bf.next = head
  
         head_idx = len(dic) - k
  
         tail_idx = head_idx - 1
         if tail_idx == -1 : tail_idx = len(dic)-1
         dic[tail_idx].next = None
         node = dic[head_idx]
  
         return dic[head_idx]