L22. Rotate a Linked List

Rotating a singly linked list involves shifting its elements to the right by $K$ places. When an element is shifted off the tail of the list, it wraps around and reappears at the head. This chapter explores how to solve this efficiently by manipulating pointer links rather than shifting node values individually, optimizing both small and exceptionally large values of $K$.

1. Why Do We Need This? (Problem Statement & Status Quo)

Given the head of a singly linked list and an integer $K$, our task is to rotate the linked list to the right by $K$ places and return the new head of the updated list.

Visualizing a Single Rotation ($K = 1$)

Consider a linked list with 5 nodes: 1 -> 2 -> 3 -> 4 -> 5 -> NULL.

• Target: Rotate right by 1 place.
• Result: The last element (5) moves to the front, and all other elements shift right by one place.
• Updated List: 5 -> 1 -> 2 -> 3 -> 4 -> NULL.

Visualizing Multiple Rotations ($K = 2$)

If we perform a second rotation on our already rotated list:

• Result: The last element (4) moves to the front.
• Updated List: 4 -> 5 -> 1 -> 2 -> 3 -> NULL.

The range of $K$ can vary drastically. $K$ might be smaller than the length of the list, equal to the length, or significantly larger (e.g., $K = 100$, $K = 1000$, or more). We must design an algorithm that handles all these cases gracefully without unnecessary loops.

2. Core Mental Model & Real-World Analogy

Real-Life Analogy: The Circular Conveyor Belt

Imagine a circular conveyor belt holding numbered items in a fixed order. If you rotate the belt to the right by 2 positions, the items at the tail end wrap around to become the new front items.

Instead of picking up each item and shifting it physically one by one (which is slow and inefficient), you can achieve the exact same state by:

1. Connecting the tail node directly back to the original head node (forming a temporary circle).
2. Cutting the circle at a new strategic point (the new tail node) and making its next pointer point to NULL.
3. Designating the node immediately following the new tail as the new head.

3. Naive vs. Better Approach

The Inefficient Approach (Value Shifting)

• Strategy: Take the last element, move it to the front, shift everything else, and repeat this process $K$ times.
• Drawback: If $K$ is very large (e.g., $K = 10^9$) or the list is long, repeating single rotations takes $O(K \times N)$ time, which will easily cause Time Limit Exceeded (TLE) errors in online judges.

The Optimal Approach (Pointer Manipulation & Modular Arithmetic)

• Strategy:
  1. Find the total length ($N$) of the linked list and locate its tail node.
  2. Optimize $K$ using modulo arithmetic: $K = K \pmod N$. If $K$ becomes $0$, no rotation is needed.
  3. Form a circular list by pointing tail->next = head.
  4. Find the new tail node, which is located at position $(N - K)$ from the start (using 1-based indexing).
  5. Set the new head to be newTail->next, and sever the circular link by setting newTail->next = NULL.

4. Step-by-Step Evolution of the Algorithm

Let us trace the algorithm using an example where the list is 1 -> 2 -> 3 -> 4 -> 5 -> NULL and $K = 2$.

Step 1: Find Length and Locate Tail

We start a traversal from the head, counting nodes and keeping track of the tail.

• head points to node 1.
• Traverse: 1 -> 2 -> 3 -> 4 -> 5.
• Length ($N$) = 5.
• Tail points to node 5.

Step 2: Handle Large $K$ via Modulo Arithmetic

If $K = 7$, rotating a list of length $5$ seven times is equivalent to rotating it $7 \pmod 5 = 2$ times.

Step 3: Connect Tail to Head

Make the tail's next pointer point to the original head to form a ring:

Step 4: Locate the New Tail

We need to find the node right before the new head.

• Since length is $5$ and $K = 2$, the last $2$ nodes (4 and 5) will move to the front.
• The new tail will be at position length - K = 5 - 2 = 3 (the 3rd node, which is value 3).
• We traverse from the head up to the $(N - K)$-th node.

Step 5: Update Head and Break the Circle

• New Head: newTail->next (which is node 4).
• Break Link: newTail->next = NULL (node 3 now points to NULL).

5. Handling Edge Cases & Robustness

When writing production-ready code, several edge cases must be checked upfront:

6. Complete Pseudocode Walkthrough

The following clean, language-agnostic pseudocode captures the complete logic for rotating a linked list:

Function rotateRight(head, K):
    // Edge case checks
    If head is NULL or head.next is NULL or K == 0:
        Return head
        
    // Step 1: Calculate length and find the tail node
    length = 1
    tail = head
    While tail.next is not NULL:
        length = length + 1
        tail = tail.next
        
    // Step 2: Handle K values greater than or equal to length
    K = K % length
    If K == 0:
        Return head
        
    // Step 3: Connect tail to head to form a circular list
    tail.next = head
    
    // Step 4: Find the new tail node at position (length - K)
    stepsToNewTail = length - K
    newTail = head
    For i from 1 to stepsToNewTail - 1:
        newTail = newTail.next
        
    // Step 5: Update head and break the circular link
    newHead = newTail.next
    newTail.next = NULL
    
    Return newHead

7. Complexity Analysis

Time Complexity: $O(2N)$ or $O(N)$

1. First Pass: Traversing the list from head to tail to compute the length takes $O(N)$ time.
2. Second Pass: Traversing from the head to the $(N - K)$-th node takes at most $O(N)$ time.
3. Overall time complexity is $O(N) + O(N) = O(2N)$, which simplifies asymptotically to $O(N)$.

Space Complexity: $O(1)$

• We only use a few pointer variables (tail, newTail, newHead) and an integer counter (length).
• No extra data structures or recursive call stacks are utilized.
• Overall auxiliary space complexity is $O(1)$ (Constant Space).

8. Summary and Key Takeaways

• Pointer Manipulation over Value Copying: Rotating linked lists should be handled by rewiring pointers (next references) rather than moving node values.
• Circular List Formation: Connecting the tail node to the initial head (tail->next = head) temporarily transforms the linear list into a circular ring, making rotation straightforward.
• Modulo Optimization: Always use K = K % length when $K$ can exceed the length of the list to eliminate redundant full rotations.
• Locating the New Tail: The new tail is always positioned at the $(N - K)$-th node from the beginning of the list.
• Severing the Ring: After identifying the new tail and updating the head (newTail->next), remember to set newTail->next = NULL to terminate the list correctly.
• Edge Case Discipline: Always guard against empty lists, single-element lists, and cases where $K$ is a direct multiple of the list length.
• Optimal Efficiency: The algorithm achieves an optimal $O(N)$ time complexity and $O(1)$ space complexity.