61. Rotate List

• python3

📎 Problem

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

Plan Solution

1. Count the lenght of the linked list.
2. Adjust the number of rotations.
3. Link with the fisrt and head node.
4. Move step one by one.

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 or not head.next or k == 0:
            return head
        
        # 1. 전체 노드 수 카운트
        length = 1
        current = head
        while current.next:
            current = current.next
            length += 1
        
        # 2. 회전 횟수 조정
        k = k % length
        if k == 0:
            return head
        
        # 3. 리스트 끝과 시작 연결
        current.next = head
        
        # 4. 새로운 헤드를 찾기 위해 분리 지점을 결정
        steps_to_new_head = length - k
        new_tail = head
        for _ in range(steps_to_new_head - 1):
            new_tail = new_tail.next
        
        # 5. 새로운 헤드 설정 및 리스트 분리
        new_head = new_tail.next
        new_tail.next = None
        
        return new_head

Result

• Time Complexity : O(n)
• Space Complexity : O(1)