Rotate a Linked List

Rotate a Linked List asks you to shift a singly linked list to the right by k places. The clever move is to stop thinking about it as "move k nodes" and instead close the list into a ring, then cut it once in the right spot.

The slow way first

The literal reading is: move one node from the tail to the front, and repeat that k times. Each move means walking to the second-to-last node to find the new tail, so one move is O(n) and k moves is O(n·k) — wasteful, and even worse when k is much bigger than the list.

The question to ask: where does every node actually end up? Rotating right by k just splits the list at one point — the last k nodes become the new front, and the rest follow. So we only need to find one new boundary, not shuffle nodes one at a time.

The idea: close the ring, then cut once

Walk to the tail and count the length n on the way. Then connect tail.next = head so the list becomes a ring with no end. Now the only question is where to cut. The new tail is the (n - k)-th node; the node right after it is the new head. Cut the ring there and you are done.

The key insight: once it is a ring, a "rotation" is just choosing the right place to break it. One pass to measure, a few steps to reach the cut, and the rotated list falls out.

Walk through it

Step through the animation. A pointer walks to node 40 (the tail) while counting n = 4. We point the tail back to node 10, drawing the ring edge underneath. Since k = 1, the new tail is the (n - k) = 3rd node — node 30 — so we step there from the head. Node 30's next (node 40) becomes the new head, and we cut the link after node 30. Following the pointers from node 40 gives 40 -> 10 -> 20 -> 30.

Pseudocode

if list is empty or has one node:
    return head                       # nothing to rotate
walk to the tail, counting nodes -> n, tail
k = k mod n                           # rotating by n changes nothing
if k == 0:
    return head
tail.next = head                      # close the list into a ring
new_tail = head
step forward (n - k - 1) times        # land on the (n - k)-th node
new_head = new_tail.next              # the node after it leads the rotation
new_tail.next = None                  # cut the ring just after new_tail
return new_head

The Python solution

def rotate_right(head, k):
    if head is None or head.next is None:
        return head
    # 1. count length, stop on the tail
    n = 1
    tail = head
    while tail.next is not None:
        tail = tail.next
        n += 1
    # 2. only k % n rotations matter
    k = k % n
    if k == 0:
        return head
    # 3. close the list into a ring
    tail.next = head
    # 4. walk to the new tail: the (n - k)-th node
    new_tail = head
    for _ in range(n - k - 1):
        new_tail = new_tail.next
    # 5. detach to get the new head
    new_head = new_tail.next
    new_tail.next = None
    return new_head

• Lines 2-3 handle the trivial cases: an empty list or a single node has nothing to rotate.
• Lines 5-9 walk tail to the last node while counting n — one pass to learn the length and grab the tail.
• k = k % n (line 11) collapses huge k values; if it reduces to 0 the list is unchanged, so we return early.
• Line 15 is the pivot of the trick: tail.next = head closes the list into a ring.
• The loop on lines 18-19 steps new_tail forward n - k - 1 times to reach the (n - k)-th node.
• new_head = new_tail.next (line 21) names the node that will lead the rotated list.
• new_tail.next = None (line 22) cuts the ring, and we return the new head.

Complexity

We touch each node a constant number of times and reuse the existing nodes — no extra list is built — so it runs in O(n) time and O(1) space. The pattern — splice the structure into a loop, then break it at the chosen point — recurs in many linked-list problems.

When this pattern shows up

Practice