Rotate List (LeetCode 61)

The problem

You get the head of a linked list and a non-negative integer k. Rotate the list to the right by k places: each step moves the last node to the front. Return the new head. k can be much larger than the list length.

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

Rotating once gives 5 1 2 3 4; rotating again gives 4 5 1 2 3.

How to think about it

Start with brute force. Do exactly what the problem says k times: walk to the second-last node, detach the tail, put it at the front. Each rotation is O(n), so the total is O(n·k). With k up to 2·10⁹, that never finishes.

First insight: rotating by n does nothing. A list of length n rotated n times is back where it started. So only k % n matters. If that is 0, return the head unchanged.

Key insight: a rotation is just a different cut point on a ring. Join the tail to the head and the list becomes a circle with no beginning. Rotating right by k means the new head is the node k from the end, which is the node at index n - k from the start. The node just before it, at n - k - 1 steps from the head, becomes the new tail. Cut the ring there and you’re done. No node moves; one link is added and one is removed.

Which pattern is this? Linked-list pointer rewiring. The tell is “rotate” or “shift by k” on a list: measure the length, reduce k, and rewire at a computed position.

Approach

1. If the list has 0 or 1 nodes, return it.
2. Walk to the tail, counting the length n.
3. Set k %= n. If k == 0, return head.
4. Close the ring: tail.next = head.
5. Walk n - k - 1 steps from head to find newTail.
6. newHead = newTail.next; break the ring with newTail.next = None.
7. Return newHead.

Solution

def rotate_right(head, k):
    if not head or not head.next: return head
    n = 1; tail = head
    while tail.next: tail = tail.next; n += 1     # length and last node
    k %= n                                        # rotating by n is a no-op
    if k == 0: return head
    tail.next = head; steps = n - k; newTail = head   # close the ring
    for _ in range(steps - 1): newTail = newTail.next # n - k - 1 steps
    newHead = newTail.next; newTail.next = None       # cut the ring
    return newHead
# rotate_right([1,2,3,4,5], 2) -> [4,5,1,2,3]

Dry run

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

Result: 4 -> 5 -> 1 -> 2 -> 3.

Complexity

• Time: O(n). One full walk to count, plus at most one more partial walk to the cut point. k doesn’t matter after the modulo.
• Space: O(1). A handful of pointers.

Edge cases and pitfalls

• Empty list or a single node: rotation changes nothing; handled by the first line.
• k a multiple of n: k % n == 0, return the head unchanged. Without this check you’d cut the ring in the wrong place.
• Huge k: never loop k times. Always reduce it modulo n first.
• Off-by-one on the cut. You need the node before the new head, so walk n - k - 1 steps, not n - k.
• Forgetting to break the ring leaves a cycle, and any later traversal loops forever.

Related problems

• Remove Nth Node From End of List (LeetCode 19): also finds “the node k from the end”, with two pointers.
• Reverse Linked List II (LeetCode 92): another walk-to-a-position-then-rewire problem.
• Linked List Cycle (LeetCode 141): what you’d be debugging if you forgot to cut the ring.