ASAPUtils
The four boundaries
For each group name:
groupPrev: node before the group;groupStart: first node, which becomes the group tail;kth: last node, which becomes the group head;groupNext: node after the group.
Save all boundaries before mutation.
Optimal solution
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(0, head);
ListNode* groupPrev = &dummy;
while (true) {
ListNode* kth = groupPrev;
for (int i = 0; i < k && kth; ++i) kth = kth->next;
if (!kth) break;
ListNode* groupNext = kth->next;
ListNode *prev = groupNext, *curr = groupPrev->next;
while (curr != groupNext) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
ListNode* oldHead = groupPrev->next;
groupPrev->next = kth;
groupPrev = oldHead;
}
return dummy.next;
}
function reverseKGroup(head, k) {
const dummy = new ListNode(0, head);
let groupPrev = dummy;
while (true) {
let kth = groupPrev;
for (let i = 0; i < k && kth; i++) kth = kth.next;
if (!kth) break;
const groupNext = kth.next;
let prev = groupNext, curr = groupPrev.next;
while (curr !== groupNext) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
const oldHead = groupPrev.next;
groupPrev.next = kth;
groupPrev = oldHead;
}
return dummy.next;
}
Why reconnection works
Starting local prev at groupNext makes the old group head point to the suffix when it becomes the
tail. After reversal, kth is the new head, so groupPrev.next = kth connects the prefix. The old
head becomes the predecessor for the next group.
Complexity
Finding group ends and reversing groups still visits each node only a constant number of times: O(n) time. Pointer variables use O(1) space.
Traps
- Reversing before proving k nodes remain.
- Initialising local prev to null and forgetting to reconnect the group tail.
- Moving groupPrev to kth instead of the old group head.
- Losing groupNext while links are changing.
- Reversing values rather than nodes, which violates the problem requirement.
Blank re-solve prompt
Draw dummy -> 1 -> 2 -> 3 -> 4 -> 5 for k=3. Label all four boundaries, reverse only the first group, and prove why nodes 4 and 5 stay untouched.