[Leetcode][Python] 61. Rotate List

리트코드 / 파이썬 / 61. Rotate List

leetcode.com/problems/rotate-list/

Rotate List - LeetCode

풀이 방법

주어진 Linked List를 k번 회전하는 문제다. 

이 문제를 읽자마자, 전에 풀었던 문제와 비슷한 방법의 풀이법이 생각났다. 

 

2020/09/19 - [Leetcode] - [Leetcode][Python] 19. Remove Nth Node From End of List

[Leetcode][Python] 19. Remove Nth Node From End of List

 

뒤에서 k만큼의 노드를 떼어 head의 앞에 붙여주기만 하면 된다.

k만큼의 노드를 먼저 떼기 위해, slow, fast 두 pointer를 아래와 같이 이용했다.

 

 

 

맨 처음, slow = fast = head로 두고, 먼저 fast를 k번 만큼 이동시킨다.

그다음엔 head에 있던 slow와, k번 만큼 이동한 fast를 함께 이동시킨다. (while, fast.next가 None이 아닐 때까지)

 

그럼 그림의 아래와 같이 slow는 3을, fast는 5를 가리키게 된다.

 

 

그런데, 만약 k가 Linked List의 길이와 같거나 크다면 어떻게 될까?

 

 

위의 예시와 같이, k가 Linked List의 길이와 같은 경우, 다시 제자리로 돌아오는 것을 알 수 있다.

 

즉, result(k) = result(k%length) 가 된다.

 

소스 코드

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def rotateRight(self, head, k):
        """
        https://leetcode.com/problems/rotate-list/
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head:
            return head

        fast = slow = head
        length = 1

        while fast.next:
            fast = fast.next
            length += 1
        fast = head

        if k >= length:
            k = k % length

        if k == 0:
            return head

        for i in range(k):
            fast = fast.next

        while fast.next:
            fast = fast.next
            slow = slow.next

        rotated = slow.next
        slow.next = None
        fast.next = head

        return rotated