Rotate List

Close the list into a ring, then cut it at n - k MOD n

time O(n)space O(1)

Rotating right by k moves the last k nodes to the front. Doing that one node at a time costs a full scan per rotation, and k can be far larger than the list. Instead, walk once to the last node while counting the length n, then link that last node back to the head. The list is now a ring, and every rotation of a ring is the same ring — only the place it is cut open differs. Reduce k to k MOD n, walk n - k - 1 steps from the head to the new tail, take its next as the new head, and break the ring there. Two partial passes, constant extra space, and k's size never matters.

Details

Animated on: list = [1,2,3,4,5], k=2. Rotate the list to the right by k places. Answer: [4,5,1,2,3].

Problem:Rotate ListMedium

Close the list into a ring, then cut it at n - k MOD n

step 1 / 12

[0]

[1]

[2]

[3]

[4]

list = [1,2,3,4,5], k=2. A singly-linked list has no length field, so the first job is to walk to the last node and count on the way: n <- 1 at the head. The last node is needed anyway, because rotation reconnects it to the head.

tail=0· arr[0] = 1

Pseudocode

1FUNCTION rotateRight(head, k)
2  IF head = NULL RETURN head
3  n <- 1, tail <- head
4  WHILE tail.next != NULL
5    tail <- tail.next
6    n <- n + 1
7  k <- k MOD n
8  IF k = 0 RETURN head
9  tail.next <- head
10  newTail <- head
11  FOR i <- 1 TO n - k - 1
12    newTail <- newTail.next
13  head <- newTail.next
14  newTail.next <- NULL
15  RETURN head

← / → step · space play · Home restart

Every step in words

Show all 12 steps

list = [1,2,3,4,5], k=2. A singly-linked list has no length field, so the first job is to walk to the last node and count on the way: n <- 1 at the head. The last node is needed anyway, because rotation reconnects it to the head.
tail -> 2, n <- 2. Still a next node, keep walking.
tail -> 3, n <- 3. Still a next node, keep walking.
tail -> 4, n <- 4. Still a next node, keep walking.
tail -> 5, n <- 5. tail.next is NULL, so this is the real last node and the list has 5 nodes.
k <- 2 MOD 5 = 2. Rotating by n brings the list back to itself, so only k MOD n matters — the constraint allows k up to 2*10^9 against n <= 500, and a loop that runs k times would never finish.
tail.next <- head. The list is now a ring: 5 points back to 1. Every rotation of a ring is the same ring — the only thing that changes is WHERE it is cut open, so the whole problem is now just finding the cut point.
The last k=2 nodes must move to the front, so the new tail is the node just before them: index n - k - 1 = 5 - 2 - 1 = 2. Start newTail at the head and take 2 steps. Counting 3 instead lands on the new head, which is the classic off-by-one.
Step 1 of 2: newTail -> 2 (index 1).
Step 2 of 2: newTail -> 3 (index 2). That is the cut point: everything after 3 moves to the front.
head <- newTail.next = 4. Read the ring from 4: 4 -> 5 -> 1 -> 2 -> 3 — already the rotated order. The ring made the last 2 nodes reach the old head with no extra pointer surgery.
newTail.next <- NULL cuts the ring after 3, and the list is [4,5,1,2,3]. One pass to count, one partial pass to find the cut: O(n) time, O(1) extra space, no matter how large k is.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Rotate List in the editor All Linked List problems Back to roadmap