Appearance
4.9.11 — Reverse Nodes in K-Group
LeetCode 25 · Hard
The problem
Reverse the list in groups of k. If the last group has fewer than k nodes, leave it alone. You must move nodes, not values.
1 → 2 → 3 → 4 → 5, k = 2 → 2 → 1 → 4 → 3 → 5
1 → 2 → 3 → 4 → 5, k = 3 → 3 → 2 → 1 → 4 → 5The pattern
You already know how to reverse a list (4.9.1). The new work is entirely in the stitching: after reversing a block, its ends have swapped, and you have to reconnect it to the block before and the block after.
For each group, four nodes matter:
groupPrev groupNext
| |
… → [ A → B → C ] → D → …
^ ^
first last (of the group)
after reversing the group:
… → [ C → B → A ] → D → …groupPrev— the last node of the previous group. Itsnextmust end up pointing atC, the new first node.A— the group's original first node, which becomes its last. Itsnextmust point atD.
Two connections per group. Get those right and the problem is done.
The other half: knowing when to stop
Before reversing a group you must confirm there are k more nodes, because an incomplete final group is left untouched. So each round starts by walking k steps forward to find groupNext. If you fall off the end first, stop.
That walk is not wasted work — it is also how you find groupNext, which you need anyway.
The solution
python
class Solution:
def reverseKGroup(self, head, k: int):
dummy = ListNode(0, head)
group_prev = dummy
while True:
# 1. is there a full group left? walk k steps
kth = group_prev
for _ in range(k):
kth = kth.next
if not kth:
return dummy.next # incomplete group — leave it
group_next = kth.next
# 2. reverse the group, ending it at group_next
prev, curr = group_next, group_prev.next
while curr is not group_next:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# 3. stitch: group_prev.next was the group's first node,
# which is now its last — so it becomes the next group_prev
new_group_prev = group_prev.next
group_prev.next = kth # kth is the new first node
group_prev = new_group_prevts
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
const dummy = new ListNode(0, head);
let groupPrev: ListNode = dummy;
while (true) {
let kth: ListNode | null = groupPrev;
for (let i = 0; i < k; i++) {
kth = kth!.next;
if (!kth) return dummy.next;
}
const groupNext = kth.next;
let prev = groupNext, curr = groupPrev.next;
while (curr !== groupNext) {
const nxt = curr!.next;
curr!.next = prev;
prev = curr;
curr = nxt;
}
const newGroupPrev = groupPrev.next!;
groupPrev.next = kth;
groupPrev = newGroupPrev;
}
}Three details do all the work.
prev starts at group_next, not at None. In the plain reversal, the last node ends up pointing at null because the list ends there. Here the group is in the middle, so its last node must point at whatever follows the group. Seeding prev with group_next makes the standard reversal loop produce that automatically — no fix-up afterwards.
The loop condition is curr is not group_next. It reverses exactly the nodes of this group and stops at the boundary.
new_group_prev is captured before the stitch. group_prev.next currently points at the group's original first node, which after reversal is its last node — and that is exactly the group_prev for the next round. Read it before overwriting group_prev.next, or it is gone.
The dummy head means the very first group needs no special case, even though reversing it changes the head of the whole list.
Trace on 1 → 2 → 3 → 4 → 5, k = 2
Round 1. group_prev = dummy. Walk 2 steps: kth = 2. group_next = 3.
Reverse 1 → 2 with prev seeded to node 3: node 1 points to 3, node 2 points to 1.
Stitch: new_group_prev = node 1. dummy.next = node 2. So the list is 2 → 1 → 3 → 4 → 5, and group_prev = node 1.
Round 2. Walk 2 steps from node 1: kth = 4. group_next = 5.
Reverse 3 → 4 with prev = node 5: node 3 points to 5, node 4 points to 3.
Stitch: new_group_prev = node 3. node1.next = node 4. List is 2 → 1 → 4 → 3 → 5, group_prev = node 3.
Round 3. Walk 2 steps from node 3: first step reaches node 5, second step is null → return.
Final: 2 → 1 → 4 → 3 → 5. ✓
Complexity
O(n) time. Each node is visited twice — once by the counting walk, once by the reversal — which is 2n, so still linear.
O(1) space. The recursive version is O(n/k) stack space and is easier to write, but it is not constant space and the problem's follow-up asks for constant.
Where this goes next
- Swap Nodes in Pairs (LeetCode 24) — this problem with
k = 2. If you can write this one, that one is free. - Reverse Linked List II — reverse a single named range. Same stitching, one group.
- Rotate List — connect the tail to the head to make a ring, then cut it in the right place.
The rule: when reversing part of a list, seed prev with whatever should follow the reversed section, and capture the new boundary node before you overwrite the pointer to it.
What the interviewer will push on
"Why does prev start at group_next?" So the group's last node points at the rest of the list automatically, instead of at null.
"How do you know a full group remains?" Walk k steps first, returning if you hit null. The same walk finds group_next.
"Why do you capture new_group_prev before stitching?" Because the stitch overwrites the pointer you would need to find it.
"Can you do it recursively?" Yes, and it is shorter, but it uses O(n/k) stack. The follow-up asks for O(1).
"What if k is 1, or larger than the list?" k = 1 reverses nothing and the list is unchanged. k larger than the list means the first group is already incomplete, so nothing happens and the original head is returned.
One thing to volunteer: draw the four pointers before writing code, and name them out loud. This problem is not conceptually hard — it is bookkeeping — and the people who fail it are the ones who started typing without the picture.
Next: 4.10 goes back to a single array and asks how it gets sorted and searched, including binary search stated in the form that generalises far beyond sorted arrays.