Reverse Nodes in k-Group
Reverse the list k nodes at a time; a final group shorter than k stays as-is.
- The number of nodes in the list is n.
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000
Intuition
Reverse nodes in k group takes a linked list and reverses it in blocks of k, leaving any final block shorter than k untouched. Both halves of that sentence carry weight: the reversal is routine, and the leftover rule is what makes the problem Hard.
The reversal itself is the standard three-pointer flip — walk the list moving each node's next to point backwards. Doing it for exactly k nodes is a small variation.
The real work is the bookkeeping around each block. Before reversing anything you must know whether k nodes actually exist ahead, because a short tail must be left alone:
- Probe forward k steps first; if you run off the end, stop and leave the rest as it is.
Reversing first and then discovering the block was short means undoing work, which is why the probe comes first.
The second difficulty is reconnection. Reversing a block turns its first node into its last, so the previous block must now point at what was the block's last node, and the reversed block must point onward at whatever follows. A dummy node before the head removes the special case where the first block changes the list's head, and a groupPrev anchor tracks the node that needs rewiring after each block.
A neat trick avoids fixing the forward link afterwards: initialise the reversal's prev to the node after the block, so the block already points onward as it is being flipped.
Reverse-linked-list applied in blocks, with two additions: probe ahead to confirm a full group exists before touching anything, and use a dummy head so the first group needs no special case. The probe-then-act discipline is the general lesson — verify the whole operation is possible before performing any of it.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
Use a dummy node before the head
Allocate a dummy whose next is the head, and return dummy.next at the end. The first block's reversal changes the head, and the dummy means that case needs no separate handling — a pattern worth reaching for whenever the head might move.
Probe for k nodes before reversing
From groupPrev, walk k steps to find the block's last node. If you hit null first, fewer than k nodes remain — return immediately, leaving the tail in its original order as the problem requires.
Reverse exactly k nodes
Run the standard prev/curr flip for k iterations. Initialise prev to the node after the block, not to null, so the reversed block's tail already points at the next block and no fix-up pass is needed.
Reconnect both ends
The block's original first node is now its last. Set groupPrev.next to the block's new first node, which is the node the probe found, then move groupPrev to that original first node — it is the anchor for the next block.
Repeat until the probe fails
Loop from the new groupPrev. Each iteration handles one block, and the loop ends naturally when the probe runs off the list, at which point the remaining short group is already correct.
Cost of the block reversal
Each node is visited by the probe once and by the reversal once, giving O(n) time with a constant factor of two. Space is O(1) for the iterative version — the recursive alternative is shorter to write but costs O(n/k) stack frames.
Solution & live demo
Common pitfalls
Reversing before confirming the group is complete
for _ in range(k):
# reverse as you gokth = group_prev
for _ in range(k):
kth = kth.next
if not kth: return dummy.nextA trailing partial group must be left untouched, but once you've started reversing you can't cheaply undo it. Probing first means you only commit when the full group is guaranteed.
Seeding prev with None instead of group_next
prev, curr = None, group_prev.next
prev, curr = group_next, group_prev.next
The reversed block's tail must point at the next group, not at null — otherwise the list is severed after the first block and everything beyond it is lost. Seeding with group_next splices the remainder on automatically.
Advancing group_prev after rewiring it
group_prev.next = kth group_prev = group_prev.next
tmp = group_prev.next group_prev.next = kth group_prev = tmp
Reversal makes the group's old head its new tail, and that node is where the next group attaches. Reading group_prev.next after the rewire gives kth — the new head — so the pointer jumps to the wrong end of the block.
Edge cases
The probe fails on the last group and it is left in original order.
Every probe succeeds but reversal of one node is identity — list unchanged.