Reverse Nodes in k-Group (LeetCode 25): A Pointer-by-Pointer Walkthrough
5 views
Reverse Nodes in k-Group asks you to reverse a linked list k nodes at a time. If the final group has fewer than k nodes, leave it as is. For 1 -> 2 -> 3 -> 4 -> 5 with k = 2, the answer is 2 -> 1 -> 4 -> 3 -> 5; with k = 3, it is 3 -> 2 -> 1 -> 4 -> 5. You must change links, not values, and the follow-up asks for O(1) extra space.
It is labeled hard mostly because of pointer bookkeeping. Break it into small, named steps and it becomes manageable.
Step 1: a dummy head
Create a dummy node pointing at the head. Keep a pointer group_prev that always sits just before the next group to reverse. Starting at the dummy means the first group needs no special case.
Step 2: find the k-th node
From group_prev, walk k steps to find kth. If you run out of nodes first, the remaining group is shorter than k and you are done. Remember group_next = kth.next, the node right after the group.
Step 3: reverse the group
Reverse nodes from group_prev.next up to kth, using the standard three-pointer reversal, but start prev at group_next instead of None. That way the last node of the reversed group already points to the rest of the list.
Step 4: reconnect
The old first node of the group is now its last node. Save it before reversing (call it first), set group_prev.next = kth, then move group_prev = first for the next iteration.
Python
def reverse_k_group(head, k):
dummy = ListNode(0, head)
group_prev = dummy
while True:
kth = group_prev
for _ in range(k):
kth = kth.next
if not kth:
return dummy.next
group_next = kth.next
first = group_prev.next
prev, cur = group_next, first
while cur is not group_next:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
group_prev.next = kth
group_prev = first
Each node is visited a constant number of times, so time is O(n) and extra space is O(1).
Recursive alternative
A recursive version reverses the first k nodes and calls itself on the rest. It is shorter but uses O(n/k) stack space, which breaks the follow-up constraint. Mention it, then explain why you chose the iterative version.
Common bugs interviewers watch for
- Reversing a short final group. Always check that k nodes exist before touching any pointers.
- Losing the rest of the list. Saving group_next first prevents it.
- Forgetting to move group_prev to the old first node.
- Off-by-one when k = 1 (the list should be unchanged) or when k equals the length.
How to present it
Draw a small example with boxes and arrows before coding, and label group_prev, first, kth, and group_next. Then dry-run one group out loud. This makes the code feel like a translation of the picture, not memorized lines.
Support during the interview
Pointer-heavy problems are where nerves cause the most mistakes. Linkjob AI (https://linkjob.ai) provides real-time help during live job interviews and technical interviews, suggesting hints and checkpoints while you work through the solution in your own words.