Rotate List

Description

Rotate List
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

Brute Force Approach

Shift the entire list to the right by $1$ node at a time, repeating the entire process $k$ times. In each iteration, traverse to the second-to-last node, detach the last node, attach it to the front as the new head, and update references.

public ListNode rotateRightBruteForce(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) return head;
 
    for (int i = 0; i < k; i++) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr.next != null) {
            prev = curr;
            curr = curr.next;
        }
        prev.next = null;
        curr.next = head;
        head = curr;
    }
    return head;
}
 

• Time Complexity: $\mathcal{O}(k\cdot n)$ — Traverses the list up to $k$ times; causes Time Limit Exceeded (TLE) when $k$ is large.
• Space Complexity: $\mathcal{O}(1)$ — Uses a constant number of pointer variables.

---

Optimized Approach (The Ring Method)

Connect the end of the list back to the head to form a circular ring, then cut the ring at the correct offset.

Mental Model Steps:

1. Form the Ring: Traverse to the end to get length $n$ and connect cur.next = head.
2. Find Split Point: Reduce $k$ via $k=k\mathrm{mod}n$. Advancing $n-k$ steps from the tail lands cur directly on the new tail node.
3. Break the Ring: Set head = cur.next, then disconnect the list using cur.next = null.

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return head;
        }
 
        ListNode cur = head;
        int n = 1;
        while (cur.next != null) {
            n++;
            cur = cur.next;
        }
 
        cur.next = head;
        k %= n;
        for (int i = 0; i < n - k; i++) {
            cur = cur.next;
        }
 
        head = cur.next;
        cur.next = null;
        return head;
    }
}
 

• Time Complexity: $\mathcal{O}(n)$ — Exactly two passes: one pass to calculate length $n$ and form the ring, and a second pass of at most $n$ steps to cut the ring.
• Space Complexity: $\mathcal{O}(1)$ — Re-links existing node pointers in place without allocating extra memory.