These are the notes for DSA episode 24, the last hard problem of the linked list block. Reverse a linked list k nodes at a time, leave a short last group alone, and do it in place with O(1) extra memory. The obvious way treats the list like an array: get(i), get(j), swap values. Every get walks from the head, so it is O(n²/k) and times out on 2 lakh nodes, and it swaps values, which the problem forbids. The fix reuses episode 21's prev / curr / next on one group at a time, with a dummy node and two bookmarks, groupPrev and groupNext: O(n) time, O(1) space. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
A train with coaches 1 to 5 reaches a yard whose turntable can only turn 3 coaches at a time (a set of coaches moved together is a rake). The yard splits the train into rakes [1 2 3] [4 5], turns each full rake ([3 2 1]), and hooks everything back together. The last rake has only 2 coaches, so it isn't turned: the train becomes 3 2 1 4 5.
| In the yard | In the code |
|---|---|
| A rake of k coaches | A group of k nodes |
| Turning a rake on the turntable | Reversing the group's links |
| The coach just before the rake | groupPrev |
| The coach just after the rake | groupNext |
| The last coach of the rake | kth |
| A short last rake | fewer than k nodes left: unchanged |
Problem statement
Given the head of a linked list and an integer k, reverse the nodes k at a time and return the new head. If fewer than k nodes remain at the end, leave them in order. Change links, not values, and use O(1) extra memory.
1->2->3->4->5, k = 2 → 2->1->4->3->5
1->2->3->4->5, k = 3 → 3->2->1->4->5
Edge cases: k = 1 (unchanged), k = n (fully reversed), k > n (unchanged), an empty list.
Brute force: pretend it's an array
Count the nodes, then reverse each full group like an array: swap the two ends, move inwards. A list has no index, so get(head, i) walks i steps.
static Node get(Node head, int i) {
while (i-- > 0) head = head.next;
return head;
}
static Node bruteK(Node head, int k) {
int n = 0;
for (Node c = head; c != null; c = c.next) n++;
for (int s = 0; s + k <= n; s += k)
for (int i = s, j = s + k - 1; i < j; i++, j--) {
Node a = get(head, i), b = get(head, j);
int t = a.val; a.val = b.val; b.val = t;
}
return head;
}
With k = 2 and k = 3 on 1..5 it printed 2 -> 1 -> 4 -> 3 -> 5 -> null and 3 -> 2 -> 1 -> 4 -> 5 -> null. Correct answers, but it swaps values.
The big input: 2 lakh nodes
A list 1..200000 with k = 3: Time Limit Exceeded.
Why the brute force fails
Every swap calls get twice, and each get walks from the head (up to n steps). With n/k groups that's about n²/k hops (≈ n²/3 for k = 3).
| Nodes | Hops (about n²/3) |
|---|---|
| 1,000 | 3 lakh |
| 20,000 | 13 crore |
| 2,00,000 | 1.3 × 10¹⁰: TLE |
And it breaks the rule: it moves values, not nodes.
The key insight: one group at a time, with bookmarks
We already reverse links in one walk (episode 21). Do it for one group, then hook the group back in. Before touching a group, mark both sides:
- From
groupPrev, walk k steps: that node iskth. If you hitnullfirst, fewer than k remain: stop. groupNext = kth.next. Reverse the group withprev / curr / next, butprevstarts atgroupNext, notnull, so the group's new tail is already hooked to the rest.groupPrev.next = kth: the group's new front. The group's old first node is now its tail.groupPrev= that old first node. Repeat.
A dummy node before the head gives even the first group a groupPrev, so changing the head isn't a special case. Return dummy.next.
Trace with k = 3 on D -> 1 -> 2 -> 3 -> 4 -> 5:
| Step | What happens | List (following arrows from D) |
|---|---|---|
| 1 | groupPrev = D; walk 3: kth = 3, groupNext = 4 | D 1 2 3 4 5 |
| 2 | reverse 1..3 with prev = 4: 1→4, 2→1, 3→2 | D 1 4 5 (D still points to 1) |
| 3 | D.next = 3; first = 1 | D 3 2 1 4 5 |
| 4 | groupPrev = 1; walk 3: 4, 5, null → stop | D 3 2 1 4 5 |
| end | return D.next | 3 2 1 4 5 |
The optimal solution in Java
public class Main {
static class Node {
int val;
Node next;
Node(int val) { this.val = val; }
}
static Node build(int... a) {
Node head = null;
for (int i = a.length - 1; i >= 0; i--) {
Node n = new Node(a[i]);
n.next = head;
head = n;
}
return head;
}
static String show(Node h) {
StringBuilder sb = new StringBuilder();
for (; h != null; h = h.next) sb.append(h.val).append(" -> ");
return sb.append("null").toString();
}
static Node reverseKGroup(Node head, int k) {
Node dummy = new Node(0);
dummy.next = head;
Node groupPrev = dummy;
while (true) {
Node kth = groupPrev;
for (int i = 0; i < k && kth != null; i++) kth = kth.next;
if (kth == null) break;
Node groupNext = kth.next;
Node prev = groupNext, curr = groupPrev.next;
while (curr != groupNext) {
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
Node first = groupPrev.next;
groupPrev.next = kth;
groupPrev = first;
}
return dummy.next;
}
public static void main(String[] args) {
System.out.println(show(reverseKGroup(build(1, 2, 3, 4, 5), 2)));
System.out.println(show(reverseKGroup(build(1, 2, 3, 4, 5), 3)));
System.out.println(show(reverseKGroup(build(1, 2, 3, 4, 5), 1)));
System.out.println(show(reverseKGroup(build(1, 2, 3, 4, 5), 5)));
System.out.println(show(reverseKGroup(build(1, 2, 3, 4, 5), 6)));
System.out.println(show(reverseKGroup(null, 2)));
}
}
Output:
2 -> 1 -> 4 -> 3 -> 5 -> null
3 -> 2 -> 1 -> 4 -> 5 -> null
1 -> 2 -> 3 -> 4 -> 5 -> null
5 -> 4 -> 3 -> 2 -> 1 -> null
1 -> 2 -> 3 -> 4 -> 5 -> null
null
On 2 lakh nodes with k = 3 it printed starts 3 2 1, 36 ms. Each node is visited about twice: once while counting k ahead, once while reversing.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node* next;
Node(int v) : val(v), next(nullptr) {}
};
Node* build(const vector<int>& a) {
Node* head = nullptr;
for (int i = (int)a.size() - 1; i >= 0; i--) { Node* n = new Node(a[i]); n->next = head; head = n; }
return head;
}
string show(Node* h) { string s; for (; h; h = h->next) s += to_string(h->val) + " -> "; return s + "null"; }
Node* reverseKGroup(Node* head, int k) {
Node dummy(0);
dummy.next = head;
Node* groupPrev = &dummy;
while (true) {
Node* kth = groupPrev;
for (int i = 0; i < k && kth; i++) kth = kth->next;
if (!kth) break;
Node* groupNext = kth->next;
Node *prev = groupNext, *curr = groupPrev->next;
while (curr != groupNext) {
Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
Node* first = groupPrev->next;
groupPrev->next = kth;
groupPrev = first;
}
return dummy.next;
}
int main() {
for (int k : {2, 3, 1, 5, 6}) cout << show(reverseKGroup(build({1, 2, 3, 4, 5}), k)) << "\n";
}
Output: the first five lines of the Java output.
The same solution in Python
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
def build(*a):
head = None
for x in reversed(a):
head = Node(x, head)
return head
def show(h):
out = []
while h:
out.append(str(h.val)); h = h.next
return " -> ".join(out + ["null"])
def reverse_k_group(head, k):
dummy = Node(0, head)
group_prev = dummy
while True:
kth = group_prev
for _ in range(k):
kth = kth.next
if kth is None:
return dummy.next # fewer than k left: leave them
group_next = kth.next
prev, curr = group_next, group_prev.next
while curr is not group_next:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
first = group_prev.next
group_prev.next = kth
group_prev = first
for k in (2, 3, 1, 5, 6):
print(show(reverse_k_group(build(1, 2, 3, 4, 5), k)))
print(show(reverse_k_group(None, 2)))
Output: the same six lines as Java.
Three real bugs
Bug 1: Node prev = null inside the group
Copying episode 21 exactly. With k = 3: 3 -> 2 -> 1 -> null. Node 1, the group's new tail, points to null, so 4 and 5 are cut off. Fix: prev = groupNext.
Bug 2: forgetting groupPrev = first
Time Limit Exceeded. groupPrev stays on the dummy, so the loop finds the same first group again and flips it back, forever.
Bug 3: return head;
With k = 3: 1 -> 4 -> 5 -> null. head still points at node 1, which is now in the middle (the first group's tail). Fix: return dummy.next.
And if you delete the if (kth == null) break;, Java refuses to compile:
Main.java:40: error: unreachable statement
return dummy.next;
^
1 error
while (true) with no break can never finish, so the return after it can never run.
Complexity
| Approach | Time | Extra space | 2 lakh nodes, k = 3 |
|---|---|---|---|
get(i) + swap values |
O(n²/k) | O(1), but swaps values | Time Limit Exceeded |
| Copy values to an array, reverse blocks | O(n) | O(n), swaps values | not allowed |
| Dummy + groupPrev + reverse | O(n) | O(1) | 36 ms |
| Recursive group reversal | O(n) | O(n/k) call stack | fine for moderate n |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
Node prev = null inside a group |
3 -> 2 -> 1 -> null |
the group's tail points to null |
prev = groupNext |
No groupPrev = first |
Time Limit Exceeded | the same group flips back and forth | move groupPrev to the old first node |
return head; |
1 -> 4 -> 5 -> null (k = 3) |
the old head is now inside the list | return dummy.next |
No if (kth == null) break; |
error: unreachable statement |
while (true) never ends |
break when no full group is left |
| Reversing the short last group | 3 -> 2 -> 1 -> 5 -> 4 (k = 3) |
didn't check the group is full | count k ahead before reversing |
| Treating the list like an array | TLE | get(i) is O(n) |
walk once with pointers |
Mini project: a bus seating chart
A bus fills seats in rows of k from the front; for the return trip each full row is reversed (window seats swap sides), and a partly filled last row keeps its order. Store passenger ids in a list and print the return-trip order with reverseKGroup(ids, k): for ids 1..8 and k = 3 it is 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8 -> null. Extension: also reverse the last partial row (practice 1).
Practice
- Reverse in groups of k, and also the last short group.
Solution
Same loop, but kth stops at the last real node instead of requiring a full group.
static Node reverseAllGroups(Node head, int k) {
Node dummy = new Node(0);
dummy.next = head;
Node groupPrev = dummy;
while (groupPrev.next != null) {
Node kth = groupPrev;
for (int i = 0; i < k && kth.next != null; i++) kth = kth.next;
Node groupNext = kth.next;
Node prev = groupNext, curr = groupPrev.next;
while (curr != groupNext) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
Node first = groupPrev.next;
groupPrev.next = kth;
groupPrev = first;
}
return dummy.next;
}
1..5, k = 3 → 3 -> 2 -> 1 -> 5 -> 4 -> null.
- Swap nodes in pairs (k = 2) without the general code.
Solution
static Node swapPairs(Node head) {
Node dummy = new Node(0);
dummy.next = head;
Node prev = dummy;
while (prev.next != null && prev.next.next != null) {
Node a = prev.next, b = a.next;
a.next = b.next;
b.next = a;
prev.next = b;
prev = a;
}
return dummy.next;
}
1..5 → 2 -> 1 -> 4 -> 3 -> 5 -> null.
- The recursive version.
Solution
Check a full group exists, reverse the rest recursively, then reverse this group with prev starting at the reversed rest.
static Node reverseKRec(Node head, int k) {
Node kth = head;
for (int i = 0; i < k; i++) {
if (kth == null) return head;
kth = kth.next;
}
Node prev = reverseKRec(kth, k), curr = head;
while (curr != kth) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
return prev;
}
1..8, k = 3 → 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8 -> null. Uses O(n/k) stack.
- Reverse every alternate group of k (reverse, skip, reverse, skip ...): after re-hooking a group, walk
groupPrevforward k more nodes before the next reversal.
Quick quiz
show(reverseKGroup(build(1, 2, 3, 4, 5, 6, 7, 8), 3))
3->2->1->6->5->4->8->7->null3->2->1->6->5->4->7->8->null8->7->6->5->4->3->2->1->null1->2->3->4->5->6->7->8->null
Answer
3->2->1->6->5->4->7->8->null. Two full groups are reversed; 7 and 8 are fewer than k, so they stay in order. (Real output: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8 -> null.)
Interview questions
- Reverse nodes in k-group in O(1) space. Dummy node; for each group count k ahead, reverse with
prev = groupNext, re-hookgroupPrev.next = kth, movegroupPrevto the old first node. - Why does
prevstart atgroupNext? So the reversed group's new tail already points to the rest of the list. - Why a dummy node? The first group changes the head; the dummy gives it a
groupPrevlike every other group. - Time complexity? O(n): each node is counted once and reversed once.
- What happens with the last short group? It is left in order (unless the variant asks otherwise).
- Iterative vs recursive? Same O(n) time; recursion uses O(n/k) stack frames.
- How is this related to "reverse a linked list"? It's the same three-pointer loop applied to a bounded section, plus re-linking the boundaries.
- Why not swap values? The problem forbids it, and real nodes may carry large or immutable data.
Glossary
| Term | Meaning |
|---|---|
| Group (of k) | k consecutive nodes reversed together |
groupPrev |
The node just before the current group (initially the dummy) |
kth |
The last node of the current group; after reversal, its new front |
groupNext |
The node just after the current group |
| Dummy node | A fake node before the head so the first group isn't a special case |
| In place | Rearranging the existing nodes without building new ones |
get(i) on a list |
Walking i steps from the head: O(i) |
prev / curr / next |
The three pointers of the reversal loop (episode 21) |
| Unreachable statement | A Java compile error for code that can never run |
| O(n²/k) | Work that grows with the square of n, divided by k |
| O(1) space | Extra memory that doesn't grow with the input |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
Summary
get(i)on a linked list is O(n), so "pretend it's an array" is O(n²/k) and times out; it also swaps values.- Use a dummy node and process one group at a time: count k ahead (stop if short), reverse with
prev = groupNext,groupPrev.next = kth,groupPrev = first. - O(n) time, O(1) extra space; return
dummy.next.
Next episode: LRU cache: hash map + doubly linked list.