You are given the head of a linked list and a number k. Reverse the nodes in groups of k: the first k nodes are reversed, then the next k, and so on. If the last group has fewer than k nodes, leave it exactly as it is. You must re-link the nodes, not swap their values.
You already know how to reverse a whole list, from 4.9.1. Reversing one group is the same loop, stopped after k nodes.
The new work is all in the stitching. After a group is reversed, its two ends have swapped places. The group must be reconnected to the node before it and to the node after it. Picture a necklace. You cut out k beads, flip that piece around, and tie it back in. To tie it back, you must keep hold of the bead just before the cut and the bead just after it. Let go of either, and the rest of the necklace falls on the floor.
So the real question is: for each group, which pointers must you hold on to, and in what order do you reconnect them?
Copy the values into an array, reverse each chunk of k values in the array, and write them back into the nodes.
python
def reverseKGroup(head, k): vals = [] node = head while node: vals.append(node.val) node = node.next for start in range(0, len(vals) - k + 1, k): # only full groups vals[start:start + k] = vals[start:start + k][::-1] node = head for v in vals: node.val = v node = node.next return head
It is O(n) time, but it uses O(n) extra memory, and it swaps values instead of re-linking nodes. Both break the rules.
The flaw in one sentence: it avoids the pointer work by copying everything out, which is exactly the skill the problem is testing.
Put a dummy node in front of the list. Then handle one group per round.
For each group, four nodes matter:
group_prev group_next | | … → [ A → B → C ] → D → … ^ ^ first kthafter reversing the group: … → [ C → B → A ] → D → …
group_prev is the node just before the group. After the reversal, it must point to C, the group's new first node.
A was the group's first node and is now its last. It must point to D, the node after the group.
kth is the group's last node, C. It becomes the group's first node.
group_next is D, the first node after the group.
Each round does three steps.
Check there is a full group. Walk k steps from group_prev. If you run out of nodes first, the remaining group is too short, so stop. This walk also finds kth, and the node after it is group_next.
Reverse the group.
Stitch it back in, and move group_prev to the group's new last node, ready for the next round.
(1) A dummy node in front of the head. Reversing the first group changes which node is the head of the whole list. With a dummy in front, the first group has a group_prev like every other group, and no special case is needed. At the very start, group_prev is the dummy.
(2) Walk k steps from group_prev to find the last node of this group, kth.
(3) Not enough nodes left. If the walk falls off the end, the remaining group is shorter than k and must stay as it is. Everything before it is already done, so we return the real head, dummy.next.
(4) The node after the group.
(5) Set up the reversal, with one twist. In the plain reversal from 4.9.1, prev starts as None, because the old first node becomes the list's last node and must point at nothing. Here the group sits in the middle of the list. Its old first node must point at group_next, the rest of the list. So we start prev at group_next. Then the normal reversal loop makes that connection automatically, with no fix-up afterwards. curr starts at the group's first node.
(6) Reverse exactly this group. The usual four lines: save the next node, turn the arrow back, step prev forward, step curr forward. The loop stops when curr reaches group_next, the boundary.
(7) Save the group's new last node before it is lost. Right now, group_prev.next still points to the group's original first node, A. After the reversal, A is the group's last node. That is exactly the node that will be group_prev for the next round. Line (8) is about to overwrite group_prev.next, so we must read it now.
(8) Connect the node before the group to the group's new first node, which is kth.
Time. Each group's nodes are walked twice: once by the check in line (2), and once by the reversal in line (6). Every node belongs to at most one group, and the leftover short group is walked once by the check. So each node is visited at most twice, which is about 2n steps, or O(n).
Space. A fixed set of pointers, no recursion, and no arrays. So the extra memory is O(1), which meets the follow-up.
You can also write it with recursion: check that k nodes exist, reverse them, and let a recursive call handle the rest of the list, attaching its result after the reversed group. It is shorter, but every group adds a waiting call on the call stack, so it uses O(n / k) memory. The follow-up asks for O(1), so the loop version is the one to give.
Swap Nodes in Pairs. This problem with k = 2. If you can write this page, that one is free.
Reverse Linked List II. Reverse one stretch from position left to right. The same stitching, for a single group.
Rotate List. Join the tail to the head to make a ring, then cut it at the right place.
The general lesson: when you reverse part of a list, start prev at whatever should follow the reversed part, and save any boundary node before you overwrite the pointer that leads to it.
"Why does prev start at group_next?" So the group's old first node points at the rest of the list automatically, instead of at None.
"How do you know a full group remains?" Walk k steps first, and stop if you hit None. The same walk finds group_next.
"Why save new_group_prev before stitching?" The stitch overwrites the only pointer that leads to it.
"Could you do it with recursion?" Yes, more shortly, but with O(n / k) memory.
One thing to volunteer: draw the four pointers before writing code, and name them out loud. This problem is not hard in idea. It is bookkeeping, and the people who fail it are the ones who start typing before they have the picture.
Next:4.9.12 LFU Cache. Beyond the NeetCode list: the follow-up interviewers ask right after LRU, where the key to throw out is the one used least often.