58. Rotate List

Rotating a list of length n by k is the same as rotating by k % n. Once we know the length, we just need to find the new tail (at index n - k - 1) and rewire it.

Approach

1. Walk the list once to compute its length n (and find the original tail).
2. Set k = k % n. If k == 0, return head unchanged.
3. Walk to the node at position n - k - 1 — this becomes the new tail.
4. Its next is the new head. Set the original tail's next to the old head, and the new tail's next to None.

Edge cases

• Empty list or k == 0: return as-is.
• k larger than n: the modulo handles it.

Complexity

• Time: O(n) — two passes.
• Space: O(1) — pointer rewiring only.

import java.util.*;

class Solution {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

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

If we close the list into a circle first, picking a rotation just means choosing where to break the circle. The whole task becomes: find the new tail and snip there.

The mental picture

Take the list 1 → 2 → 3 → 4 → 5 and rotate it right by k = 2. The answer is 4 → 5 → 1 → 2 → 3.

If we close the list into a circle by connecting the tail back to the head:

1 → 2 → 3 → 4 → 5
↑               ↓
└───────────────┘

Now rotating right by k is just a question of where to break the circle. We want to leave k nodes "after" the break and n - k nodes "before" it. So:

• The new head is the node at position n - k (0-indexed) from the original head.
• The new tail is the node just before the new head — at position n - k - 1.

For n = 5, k = 2: new tail is at index 5 - 2 - 1 = 2 (the node 3), new head is at index 3 (the node 4). Cutting after 3 and before 4 gives 4 → 5 → 1 → 2 → 3. ✓

Steps

1. Edge cases: if head is empty or k == 0, return head unchanged.
2. Find the length n by walking the list once. While walking, also remember the original tail.
3. Reduce k: if k % n == 0, the rotation is a no-op — return head. Otherwise k = k % n.
4. Walk to the new tail: start a pointer at head and step it forward n - k - 1 times. The pointer now sits on the new tail.
5. Rewire:
   • The new head is new_tail.next.
   • Set new_tail.next = None (the new last node has no successor).
   • Walk to the end of the new list and link it back to the original head, completing the rotation.

Walk-through

head = [1,2,3,4,5], k = 2.

Edge cases

• Empty list (head is None): return immediately.
• k == 0 or k % n == 0: rotating by a multiple of the length leaves the list unchanged.
• k > n: the modulo handles it. k = 2_000_000_000, n = 5 collapses to a small offset.

Complexity

• Time: O(n) — one pass to count, one pass to find the new tail.
• Space: O(1) — only pointer rewiring.