Rotate List

Difficulty: Medium
Topics: Linked List, Two Pointers
Link: https://leetcode.com/problems/rotate-list/

Problem Description

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

Solution

1. Problem Deconstruction

Technical Reformulation
Given a singly-linked list with n nodes and integer k, perform a right rotation by k positions such that:

The last (k mod n) nodes are moved to the front
The original (n - (k mod n))-th node becomes the new tail
The original tail connects to the original head
Return the new head node after rotation

Beginner-Friendly Explanation
Imagine a line of people holding shoulders. You need to move the last k people to the front while maintaining their order. If k is larger than the line length, you only need to move the remainder after dividing by line length.

Mathematical Formulation
Let L = {v₁ → v₂ → ... → vₙ} be a linked list. Define rotation operation R(L,k) where:

Effective rotations: k' = k mod n (when n > 0)
Partition index: p = n - k'
New list: R(L,k) = {v_{p+1} → v_{p+2} → ... → vₙ → v₁ → v₂ → ... → v_p}

Constraint Analysis

0 ≤ nodes ≤ 500: Allows O(n²) solutions but optimal should be O(n)
-100 ≤ Node.val ≤ 100: No impact on algorithm, only storage
0 ≤ k ≤ 2×10⁹: Critical! Must handle k >> n via k mod n
Hidden edge cases: Empty list, single node, k = 0, k = n, k multiples of n

2. Intuition Scaffolding

Real-World Metaphor
Like rotating a conveyor belt of products - the last k items loop back to the beginning while maintaining relative order.

Gaming Analogy
In a circular dungeon map, rotating the viewpoint by k steps makes different segments appear first while preserving connectivity.

Math Analogy
Similar to modular arithmetic where list positions are mapped via (i + k') mod n transformation.

Common Pitfalls

Not handling k > n (causes unnecessary rotations)
Forgetting to update both new tail and new head
Not considering empty/single-node lists
Incorrectly calculating break point
Creating cycles without proper termination

3. Approach Encyclopedia

Brute Force (k Rotations)

Pseudocode:
for i = 1 to k:
    find current_tail and previous_tail
    previous_tail.next = null
    current_tail.next = head
    head = current_tail

Time: O(k×n) → O(10⁹×500) = 5×10¹¹ ops (infeasible)
Space: O(1)

Two-Pass Optimal

1. Find length n and original tail
2. Calculate effective k = k mod n
3. Find new tail at position (n - k)
4. Reconnect: new_tail.next = null, old_tail.next = head

Time: O(2n) → O(n)
Space: O(1)

Visualization

Initial: 1 → 2 → 3 → 4 → 5 → ∅, k=2
Step 1: Find length=5, tail=5
Step 2: k' = 2 mod 5 = 2
Step 3: New tail at position 3 (5-2): 3
Step 4: 5 → 1, 3 → ∅
Result: 4 → 5 → 1 → 2 → 3 → ∅

4. Code Deep Dive

def rotateRight(head: ListNode, k: int) -> ListNode:
    # Edge case: empty list or single node
    if not head or not head.next:
        return head
    
    # Step 1: Find length and original tail
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1
    
    # Step 2: Calculate effective rotations
    k = k % length
    if k == 0:  # No rotation needed
        return head
    
    # Step 3: Find new tail (at position length - k)
    new_tail = head
    for _ in range(length - k - 1):
        new_tail = new_tail.next
    
    # Step 4: Reconnect nodes
    new_head = new_tail.next
    new_tail.next = None
    tail.next = head
    
    return new_head

Edge Case Handling

head = [0,1,2], k = 4: length=3, k=1, new tail at position 2
head = [], k = 100: Returns immediately due to empty check
head = [1], k = 999: Returns head due to single node check

5. Complexity War Room

Hardware Analysis

500 nodes × 8 bytes = 4KB (fits in L1 cache)
2 passes = ~1000 operations (negligible)

Approach Comparison

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(kn)	O(1)	8/10	❌ Fails large k
Two-Pass	O(n)	O(1)	9/10	✅ Optimal solution

6. Pro Mode Extras

Variants

LC 61: Exactly this problem
Left Rotation: Move first k elements to end
Circular Buffer: Maintain rotation state for multiple operations
Doubly-Linked: Enables O(1) rotations with circular list

Interview Cheat Sheet

Always check empty/single-node first
Mention k mod n optimization immediately
Draw diagram for connection steps
Test with k=0, k=n, k>n cases

#61 - Rotate List