[Leetcode/파이썬] 61. Rotate List

Rotate List

---

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

 

Example 1:

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

Example 2:

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

 

Constraints:

• The number of nodes in the list is in the range [0, 500].
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None or head.next is None :
            return head

        length = 0
        node = head
        while node :
            length += 1
            node = node.next
        
        k %= length

        for _ in range(k) :
            tail = self.get_tail(head)
            tail.next = head
            head = tail
        
        return head


    def get_tail(self, node: Optional[ListNode]) -> Optional[ListNode] :
        prev = node
        node = node.next

        while node.next :
            prev = node
            node = node.next

        prev.next = None
        return node

링크드 리스트 구현 문제이다.

get_tail 함수는 기존에 다른 문제에서 본 적 있는 형태이기 때문에 간단하게 설명하면, 포인터를 하나씩 오른쪽으로 옮기는 행위라고 생각하면 된다. 그 마지막 부분에서 while 문이 정지하기 때문에 결국 node.next만 남게 된다. 이게 결국 head에서 꼬리에 해당하는 가장 마지막 부분이 될 것이다. 

rotateRight 함수는 idx + 1 하는 행위이면서 가장 끝에 있는 노드를 가장 앞으로 가져오는 행위라고 생각하면 된다. 꼬리를 가장 앞으로 가져오면서 그 뒤에는 head.next를 붙이게 되기 때문에 n-1, 0~(n-2) 인덱스만 보게 되면 이런식으로 붙여지게 된다. head는 tail 변수인 get_tail 함수를 지나면서 idx = n-1 부분을 제외하고 0~(n-2) 부분이 head가 되면서 for _ in range(k) 를 진행되면서 tail 전체가 (n-1), 0, 1, 2, 3, ..., (n-2) 순서대로 정렬되고 head = tail이 되는 식이다. 

이런거 어떻게 생각해내냐...