Reverse Nodes in k-Group
Reverse a linked list k nodes at a time in O(1) extra space: find each group of k, reverse it in place, and relink it to the rest.
Problem Understanding
Reverse Nodes in k-Group: reverse the nodes of a linked list k at a time and return the new head. If the number of nodes left at the end is less than k, leave them as they are. Change the links, not the values.
Example: head = [1, 2, 3, 4, 5], k = 2 returns [2, 1, 4, 3, 5]; with k = 3 it returns [3, 2, 1, 4, 5].
The Intuition: Reverse a Sublist, Repeatedly
This is Reverse Linked List applied to one window of k nodes at a time. The difficulty is purely the bookkeeping around each window:
- groupPrev is the node just before the next group (start with a dummy before the head).
- Walk
ksteps fromgroupPrevto find kth. If the list ends first, stop: the tail stays as it is. - Reverse the group with the usual
prev/curloop, but startprevat kth.next, so the reversed group already points at the rest of the list. - Set
groupPrev.next = kth(the new front), and movegroupPrevto the group's old first node, which is now its last.
Each node is visited a constant number of times: O(n) time, O(1) space.
Interactive Walkthrough
k = 2 · WIDER GAPS MARK GROUP BOUNDARIES
DUMMY BEFORE HEAD
→
→
→
→
group
—
final
0
nodes
5
Put a dummy node before the head; groupPrev starts at the dummy. Groups of k = 2
Next
Walk 2 steps from groupPrev: the group is 1 → 2, and kth = 2
head
k
Legend & Complexity
The group of k being handled
Groups already reversed and linked
Not reached yet, or the short tail left as is
Time
O(n)
Space
O(1)
The list is drawn in its current order, with wider gaps at group boundaries. The group being found or reversed is filled; finished groups are shaded. Watch the last few nodes stay put when fewer than k remain.
Dry Run Table
Input: [1, 2, 3, 4, 5], k = 2
| Round | Group found | After reversing | List |
|---|---|---|---|
| 1 | 1 → 2 | 2 → 1 | 2, 1, 3, 4, 5 |
| 2 | 3 → 4 | 4 → 3 | 2, 1, 4, 3, 5 |
| 3 | only 5 left | — | 2, 1, 4, 3, 5 |
The Solution Template
Iterative, with a dummy node and in-place reversal of each group.
Reverse Nodes in k-Group Code
1var reverseKGroup = function(head, k) {2 const dummy = new ListNode(0, head);3 let groupPrev = dummy;4 while (true) {5 let kth = groupPrev;6 for (let i = 0; i < k; i++) {7 kth = kth.next;8 if (!kth) return dummy.next;9 }10 const groupNext = kth.next;11 let prev = groupNext, cur = groupPrev.next;12 while (cur !== groupNext) {13 const nxt = cur.next;14 cur.next = prev;15 prev = cur;16 cur = nxt;17 }18 const first = groupPrev.next;19 groupPrev.next = kth;20 groupPrev = first;21 }22};
Edge Cases & Common Mistakes
- Short tail: fewer than k nodes at the end stay in order; check the count before reversing.
- k = 1: every group is one node and the list is unchanged.
- Losing the rest of the list: start
prevatkth.next, or save it before reversing. - Moving groupPrev to kth: after reversing, kth is the group's front; the next groupPrev is the old first node, now at the back.
Summary
Keep a dummy before the head and a groupPrev pointer. Each round, find k nodes, reverse them in place with prev starting after the group, point groupPrev at the new front, and advance groupPrev to the group's old first node. Stop when fewer than k nodes remain. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet