Rotate List

Medium#61n apart

You get the head of a linked list and a number k. Turn the list to the right k times: each turn moves the last node to the front. Return the new head. Our example: 3 → 8 → 1 → 6 → 4, k = 7 — the answer is 6 → 4 → 3 → 8 → 1.

61 Rotate ListWalkthrough · 1×

Example: turn 3 → 8 → 1 → 6 → 4 to the right k = 7 times: more turns than nodes.

none38164head
node, countingslowfastthe turned list

head is 3, not none: the list is not empty

01/37
restart · back · play · step
Speed
1function rotateRight(head, k):
2 if head is none:
3 return none
4 length = 0
5 node = head
6 while node is not none:
7 length = length + 1
8 node = node.next
9 k = k mod length
10 fast = head
11 slow = head
12 repeat k times:
13 fast = fast.next
14 while fast.next is not none:
15 slow = slow.next
16 fast = fast.next
17 fast.next = head
18 head = slow.next
19 slow.next = none
20 return head
state
head
3
k
7
length
–
node
–
fast
–
slow
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every length turns bring the list back to where it was, so only k mod length turns matter. k can be far larger than the list, so the length is counted first.
  2. Turning by k moves the last k nodes to the front. fast goes k nodes ahead, and when it is on the tail, slow is right before those k nodes: the node to cut after.
  3. Three links do the turn: the tail to the old head, head to slow.next, slow.next to none. With k mod length = 0 slow ends on the tail, and the same three links give back the list unchanged.

Complexity

Time O(n): one pass to count, then fast walks the list once more; k itself does not matter after the mod. Memory O(1): a few pointers, and the nodes are relinked, not copied.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.