Problem Statement in English

You’re given the head of a linked list and an integer k. Rotate the list to the right by k places, and return the new head.

Approach

The easiest way to sovle these rotation problems on linked lists is to first connect the tail to the head to form a ring. Then we can easily find the new tail and new head by counting the number of nodes. Finally, we break the ring and return the new head.

The cut position is at (total - k - 1) steps from the old head, where total is the length of the linked list.

Solution in Python


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. Find the length and the actual tail node
        total = 1
        tail = head
        while tail.next:
            tail = tail.next
            total += 1
            
        # 2. Find effective rotations
        k %= total
        if k == 0:
            return head
            
        # 3. Connect tail to head to form a ring
        tail.next = head
        
        # 4. Find the new tail: (total - k - 1) steps from the start
        new_tail_steps = total - k
        new_tail = head
        for _ in range(new_tail_steps - 1):
            new_tail = new_tail.next
            
        # 5. Set the new head and break the ring
        new_head = new_tail.next
        new_tail.next = None
        
        return new_head

Complexity

  • Time: $O(n)$
    Since we traverse the linked list a few times, but each traversal is O(n).

  • Space: $O(1)$
    Since we only use a constant amount of extra space.

And we are done.