LeetCode - 61. Rotate List

[LeetCode] 61. Rotate List

LeetCode 61번 문제를 풀어보았다.. Link

Problem

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

Intuition

Singly LinkedList를 오른쪽 방향으로 회전시키는 문제이다.

회전하면서 새로운 Head 노드의 이전 노드로 간 다음, 링크를 끊은 다음 마지막 노드와 원래의 Head를 연결하는 방법으로 풀 수 있다.

Approach

1. 마지막 노드 last를 찾는다.
2. 새로운 Head 노드가 될 노드의 이전 노드로 이동한다.
3. 이전 노드에서 새로운 Head 노드와의 연결을 끊는다.
4. 마지막 노드 last와 원래의 head를 연결한다.

Complexity

• Time complexity:

  모든 Node의 개수를 N이라고 할 때 \(O(N)\)

• Space complexity: \(O(1)\)

My Code

# 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 not head:
            return head

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

        start_point = k % length
        if start_point == 0:
            return head

        current = head
        # To remove the link with the new head
        for _ in range(length - start_point -1):
            current = current.next
        new_head = current.next
        current.next = None
        last.next = head
        return new_head

last 노드를 찾으면서 Linked List의 길이 length를 같이 구해주어야한다.

k와 length를 % 연산 하는 이유는 length만큼 회전하면 List는 그대로이기 때문이다.

새로운 head인 new_head의 이전 노드로 가기위해 for문은 (length-start_point-1) 만큼 반복된다.