Rotate List — Solution

Problem

Given a linked list and an integer k, shift every node k positions to the right — nodes that fall off the tail wrap around to the front. If k is larger than the list length, only the remainder after dividing by the length matters.

[1,2,3,4,5]

• Input: head = [1,2,3,4,5], k = 2
• Output: [4,5,1,2,3]
• Explanation: The last 2 nodes move to the front, pushing the others to the right.

A second example shows why reducing k matters:

• Input: head = [0,1,2], k = 4
• Output: [2,0,1]
• Explanation: 4 % 3 = 1 effective rotation; only the last node moves to the front.

Intuition

A right-rotation by k is the same as taking the last k nodes and prepending them to the front. The trick is that rotating a list of length L by L is the same as doing nothing, so only k % L rotations actually matter. Once we know the effective count, we need to find where the new tail is — everything before it stays put, everything after it jumps to the front.

Solution — Circle and Cut

Connect the list into a ring, locate the new tail (L − k positions from the head), and break the circle there.

1. Walk to the end of the list to get both the length L and a pointer to the tail
2. Compute the effective rotation: k_eff = k % L; if it is 0, return head unchanged
3. Close the list into a ring by linking tail back to head
4. Advance L − k_eff − 1 steps from head to reach the new tail
5. Save new_tail.next as the new head, then set new_tail.next = None to break the ring
6. Return the new head

1class Solution:
2    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
3        if not head or not head.next or k == 0:
4            return head
5
6        # find length and the tail in one pass
7        length = 1
8        tail = head
9        while tail.next:
10            length += 1
11            tail = tail.next
12
13        k_eff = k % length
14        if k_eff == 0:           # rotating by a multiple of length is a no-op
15            return head
16
17        tail.next = head         # close the ring
18
19        # new tail sits L - k_eff positions from the head (1-indexed)
20        # so advance L - k_eff - 1 steps
21        new_tail = head
22        for _ in range(length - k_eff - 1):
23            new_tail = new_tail.next
24
25        new_head = new_tail.next  # first node of the rotated suffix
26        new_tail.next = None      # cut the ring to re-form a linear list
27        return new_head

Time: O(L) — one pass to find the length and tail, then at most one more pass to locate the new tail.
Space: O(1) — only a handful of pointers; the list nodes are rearranged in place.

Complexity Summary

Common Mistakes

• Skipping k = k % L — a value of k larger than L (e.g. k=1,000,000 on a 5-node list) would advance the pointer far past the end of the (now-circular) list without the modulo reduction, reaching the wrong position.
• Advancing L − k steps instead of L − k − 1 — this puts the pointer on the new head, not the new tail, so new_tail.next points to the node after the new head rather than the new head itself.
• Forgetting to break the ring — after cutting the list, new_tail.next must be set to null; leaving tail.next = head intact turns the returned list into an infinite cycle.
• Returning head when k equals 0 only before the modulo — k=5 on a 5-node list reduces to 0 after the modulo and also requires an early return; a check before modulo alone will miss this and may produce a wrong result when the loop runs 0 iterations but the ring is never broken.
• Not guarding against a one-node list — if head.next is null, dividing by length works (length=1, kEff=0), but closing the ring sets head.next = head and the loop then steps into an infinite cycle if the early-return check is absent.

Related Problems

• remove-nth-node-from-end-of-list — also finds a node a fixed number of positions from the end before relinking
• middle-of-the-linked-list — uses list length to target a specific position, the same sub-problem solved here
• odd-even-linked-list — splits a list into two groups and reconnects the tail of one to the head of the other
• rotate-array — the same right-rotation operation on arrays, solved with in-place reversals
• reorder-list — multi-step list restructuring: find a midpoint, reverse a half, then interleave