Rotate List — Circular Reconnection With Length Normalization

Problem Statement#

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

Constraints:

• The number of nodes in the list is in the range [0, 500]
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 10^9

Example 1:

Input:  head = [1, 2, 3, 4, 5], k = 2
Output: [4, 5, 1, 2, 3]
Explanation: Rotate right by 1: [5,1,2,3,4]. Rotate right by 2: [4,5,1,2,3].

Example 2:

Input:  head = [0, 1, 2], k = 4
Output: [2, 0, 1]
Explanation: k=4 with length 3 means k mod 3 = 1 effective rotation.

Example 3:

Input:  head = [1, 2, 3], k = 3
Output: [1, 2, 3]
Explanation: k=3 equals length — full rotation, list unchanged.

Why This Problem Matters#

Rotate List (LeetCode 61) is a medium problem that Amazon and Microsoft use to test two things simultaneously: handling large k values with modular arithmetic, and the circular reconnection technique for linked list rotation. Both aspects need to be correct for the solution to work.

The most common mistake candidates make is failing to normalize k before rotating. The problem allows k up to 2 * 10^9, far larger than the maximum list length of 500. Without k = k % n, you'd attempt an enormous number of rotation steps. This is a correctness test as much as an algorithm test — production code that handles edge cases properly.

The core algorithm — make the list circular, find the new tail, break the circle — is elegant and generalizes. The same circular-reconnect technique appears in finding the last node, detecting where a cycle was introduced, and certain scheduling algorithms where you need to rotate through a circular buffer.

The Core Insight#

Rotating a list of length n right by k positions is equivalent to rotating by k % n positions (since rotating by n positions returns to the original). If k % n == 0, the list is unchanged.

After normalizing k, the new tail of the rotated list is at position n - k - 1 from the start (0-indexed). The new head is the next node.

Technique: connect the original tail to the original head (making it circular), then walk n - k steps from the head to find the new tail, break the circle there, and return the new head.

Why n - k? Rotating right by k means the last k nodes move to the front. The new head is n - k positions from the original head (0-indexed). The new tail is one before it.

Visual Dry Run#

Input: 1 -> 2 -> 3 -> 4 -> 5, k = 2

Step 1: Find length and tail. Walk the list: length n = 5. Tail = node 5.

Step 2: Normalize k. k = 2 % 5 = 2. No early exit.

Step 3: Make circular. tail.next = head → 5 -> 1 -> 2 -> 3 -> 4 -> 5 -> ... (circular)

Step 4: Find new tail. New tail is at position n - k - 1 = 5 - 2 - 1 = 2 from head (0-indexed) = node at index 2 = node 3.

Walk 2 steps from head: head(1) -> 2 -> 3. New tail = node 3.

Step 5: Break circle. New head = new_tail.next = node 4. new_tail.next = None.

Output: 4 -> 5 -> 1 -> 2 -> 3

New head at index 3, new tail at index 2. Confirmed.

Solution (Optimal)#

Python#

def rotateRight(head, k):
    # Edge cases: empty list, single node, or no effective rotation
    if not head or not head.next or k == 0:
        return head
 
    # Step 1: find length and reach the tail
    tail = head
    n = 1
    while tail.next:
        tail = tail.next
        n += 1
 
    # Step 2: normalize k
    k = k % n
    if k == 0:
        return head  # full rotation — no change
 
    # Step 3: make circular
    tail.next = head
 
    # Step 4: find new tail (n - k steps from head)
    new_tail = head
    for _ in range(n - k - 1):
        new_tail = new_tail.next
 
    # Step 5: break circle and return new head
    new_head = new_tail.next
    new_tail.next = None
    return new_head

Time complexity: O(n) — one pass to find length + one pass to find new tail.

Space complexity: O(1) — only pointer variables.

JavaScript#

var rotateRight = function(head, k) {
    if (!head || !head.next || k === 0) return head;
 
    // Find length and tail
    let tail = head, n = 1;
    while (tail.next !== null) {
        tail = tail.next;
        n++;
    }
 
    k = k % n;
    if (k === 0) return head;
 
    // Make circular
    tail.next = head;
 
    // Find new tail
    let newTail = head;
    for (let i = 0; i < n - k - 1; i++) {
        newTail = newTail.next;
    }
 
    // Break circle
    const newHead = newTail.next;
    newTail.next = null;
    return newHead;
};

Complexity:

Common Mistakes#

1. Not normalizing k with k % n. If k = 2,000,000,000 and n = 5, rotating by k positions is the same as rotating by 0 positions. Without k % n, you'd loop 2 billion times. Always normalize.

2. Forgetting to check k == 0 after normalization. If k % n == 0, the list is unchanged. Return head early to avoid unnecessary work.

3. Off-by-one in "find new tail" step. New tail is at index n - k - 1 (0-indexed). To reach it from head, walk n - k - 1 steps (the loop runs n - k - 1 times, starting at head). Common error: walk n - k steps, which lands on the new head instead of the new tail.

4. Forgetting to break the circle. After setting new_head = new_tail.next, you must set new_tail.next = None. Without this, the list remains circular and any traversal will loop forever.

5. Not handling the empty or single-node list. head = None → tail = None and tail.next crashes. Always guard with if not head or not head.next.

Interview Tips#

1. Lead with k normalization: "The key insight is that rotating by n positions returns to the original. So k = k % n gives the effective rotation. If that's 0, no rotation needed."

2. Explain the circular technique: "I connect the tail to the head, making it circular. Then I find the new tail at position n - k - 1 and break the circle there."

3. Verify the off-by-one: Walk through [1, 2, 3, 4, 5] with k=2 on the whiteboard. Show that n - k - 1 = 2 steps from head lands on node 3 (index 2), the new tail.

4. Handle k=n explicitly: Walk through k=5 on a 5-node list. After normalization, k=0 → return head unchanged.

5. Mention the edge cases: Empty list, single node, k=0, k multiple of n — cover all four.

Follow-up Questions#

Q: How do you rotate left instead of right? Left rotation by k is equivalent to right rotation by n - k. Apply the same algorithm with k = n - k.

Q: What if you need to rotate multiple times with different k values? Precompute the cumulative effective rotation (mod n). A single rotation pass with the final k is more efficient than chaining rotations.

Q: Can you rotate in O(1) space without making the list circular? Yes — the circular technique is one approach. An alternative: walk to the (n-k-1)th node, save it as new tail. Its next is new head. Set new_tail.next = None, old_tail.next = old_head. Same O(n) time, O(1) space. The circular technique is slightly more elegant.

Q: What if k is negative (rotate left)? Not in this problem's constraints, but: normalize negative k by adding n until non-negative: k = ((k % n) + n) % n.

Q: What if the list is doubly linked? Same algorithm — additionally update prev pointers when breaking and reconnecting. New head's prev becomes None; old tail's next connects to old head; old head's prev becomes new tail.

Key Takeaways#

• Always normalize: k = k % n — rotating by n is a no-op; avoid the return-early if k == 0 only after normalization.
• The circular technique: connect tail to head, find new tail at n - k - 1 steps from head, break there.
• Off-by-one: walk n - k - 1 steps (0-indexed) to land on the new tail, not the new head.
• Always set new_tail.next = None after the reconnection — break the circle explicitly.
• Early exits: empty list, single node, k == 0 after normalization — all return head unchanged.
• Time O(n), Space O(1) — two traversal passes total.