Reverse Nodes in k-Group

Hard#25reverse

You get a linked list and a number k. Reverse the nodes in groups of k: the first k, then the next k, and so on. If fewer than k nodes are left at the end, they keep their order. Only links may change, not the values. Our example: 4 → 1 → 7 → 3 → 9 → 2 → 8 → 5, k = 3 — the answer is 7 → 1 → 4 → 2 → 9 → 3 → 8 → 5.

25 Reverse Nodes in k-GroupWalkthrough · 1×

Example: 4 → 1 → 7 → 3 → 9 → 2 → 8 → 5, k = 3: two whole groups and 2 nodes left over.

nonedummy41739285
not touchedbefore, in front of the groupcounted / next, savedcurturned around

A dummy node in front of the head: the first group gets a node before it too

01/78
restart · back · play · step
Speed
1function reverseKGroup(head, k):
2 dummy = new node whose next is head
3 before = dummy
4 while true:
5 end = before
6 repeat k times:
7 end = end.next
8 if end is none:
9 return dummy.next
10 first = before.next
11 prev = none
12 cur = first
13 repeat k times:
14 next = cur.next
15 cur.next = prev
16 prev = cur
17 cur = next
18 before.next = prev
19 first.next = cur
20 before = first
state
before
–
end
–
first
–
prev
–
cur
–
next
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. end counts k nodes before a single link changes, so a short tail is found while it is still intact and is left as it is.
  2. Each group is reversed by the card's loop, run exactly k times; after it, prev is the group's new first node and cur the first node after the group.
  3. before.next = prev and first.next = cur sew the group back in, and the old first node, now its last, becomes before for the next group.

Complexity

Time O(n): every node is counted once and turned around at most once. Memory O(1): a few pointers and one dummy node.

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.