Foundation · Module 10 · Lesson 3
In-place reversal
Reverse links while preserving the remaining chain.
Lesson 55 of 123
1d streakThe 3-Pointer Invariant: State Machine for In-Place Reversal
In-place linked list reversal redirects node forward pointers backwards without allocating new node wrappers. Reorienting a unidirectional link from A -> B to B -> A destroys the forward reference to the remainder of the list. To preserve continuity, we maintain a 3-pointer state machine: prev (tail of reversed prefix), curr (current node under inversion), and next (temporary buffer anchoring the unreversed suffix).
| Step | Action | curr | prev | next | Chain State (Input: 1 -> 2 -> 3 -> null) |
|---|---|---|---|---|---|
| 0 | Init | Node(1) | null | null | 1 -> 2 -> 3 -> null |
| 1a | next = curr.next | Node(1) | null | Node(2) | Buffer successor Node(2) |
| 1b | curr.next = prev | Node(1) | null | Node(2) | null <- 1 2 -> 3 -> null |
| 1c | prev = curr | Node(1) | Node(1) | Node(2) | Reversed prefix head is 1 |
| 1d | curr = next | Node(2) | Node(1) | Node(2) | Advance to next node |
| 2 | Cycle 2 complete | Node(3) | Node(2) | Node(3) | null <- 1 <- 2 3 -> null |
| 3 | Cycle 3 complete | null | Node(3) | null | null <- 1 <- 2 <- 3 |
The 4-Line Atomic Swap Order
next = curr.next; curr.next = prev; prev = curr; curr = next; is strictly mandatory. Mutating curr.next before buffering it in next drops the unvisited suffix forever. Advancing curr before updating prev sets prev to the wrong reference.// Canonical Iterative In-Place Reversal: O(n) Time, O(1) Space
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextNode = curr.next; // 1. Buffer forward bridge
curr.next = prev; // 2. Reverse pointer direction
prev = curr; // 3. Slide prev forward
curr = nextNode; // 4. Slide curr forward
}
return prev; // prev is now pointing to the new head
}Active Recall Checkpoint
Why does the loop terminate with return prev; instead of return curr;?
Show answer & explanation
When the loop exits, curr has stepped onto null (past the original tail). The variable prev references the last successfully reversed node, which is the new head of the inverted list.
Iterative vs Recursive Reversal: Stack Frames vs Pointer Redirection
Linked list reversal can also be formulated recursively via divide-and-conquer: assume the suffix head.next is already completely reversed, then wire head.next.next = head and break the old cycle via head.next = null. While mathematically elegant, recursion incurs an O(n) auxiliary call stack cost.
Architectural Boundary · Do Not Confuse
Iterative Reversal
Recursive Reversal
Iterative reversal consumes strictly O(1) auxiliary space and works for arbitrary lengths. Recursive reversal consumes O(n) activation stack frames; lists exceeding 10,000 nodes reliably trigger java.lang.StackOverflowError in production runtimes.
public ListNode reverseListRecursive(ListNode head) {
// Base case: empty list or single node is trivially reversed
if (head == null || head.next == null) {
return head;
}
// Recursively reverse suffix; newHead is the original tail
ListNode newHead = reverseListRecursive(head.next);
// Handshake: make successor point back to current head
head.next.next = head;
// Sever original forward link to prevent two-node infinite cycle
head.next = null;
return newHead;
}The Two-Node Cycle Bug
head.next = null in recursive reversal is a catastrophic error. After reversing 1 -> 2, node 2 points to node 1 via head.next.next = head. If node 1 still points to node 2 (head.next == 2), nodes 1 and 2 form an infinite circular loop 1 <-> 2, causing any subsequent traversal or serializer to hang indefinitely.Use it when
Use iterative reversal as the standard default for all production software, competitive programming, and unbounded lists.
Reconsider when
Use recursive reversal only when writing declarative or functional code in languages with guaranteed tail-call optimization (TCO), or when decomposing trees where depth is bounded by O(log n).
Sublist Reversal & Reverse Nodes in k-Group
Many advanced interview problems require bounded sublist reversals: reversing nodes between 1-based indices left and right, or reversing in contiguous blocks of length k. The core architectural challenge is managing the external connectors: preSublist (node before the reversed section) and postSublist (node after the reversed section).
- 01Deploy a Sentinel: ListNode dummy = new ListNode(0); dummy.next = head; guarantees left = 1 has a valid predecessor.
- 02Locate Predecessor: Traverse prev to index left - 1. Node start = prev.next marks the first node of the sublist.
- 03Head-Insertion Technique: Over right - left iterations, extract then = start.next and splice it directly after prev.
- 04Pointer Dance: start.next = then.next; then.next = prev.next; prev.next = then;.
// Reverse Nodes in k-Group: O(n) Time, O(1) Auxiliary Space
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k <= 1) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode groupPrev = dummy;
while (true) {
// 1. Verify k nodes exist in current group
ListNode kth = groupPrev;
for (int i = 0; i < k && kth != null; i++) {
kth = kth.next;
}
if (kth == null) break; // Fewer than k nodes remain, preserve order
ListNode groupNext = kth.next;
// 2. Reverse k nodes in-place
ListNode prev = groupNext;
ListNode curr = groupPrev.next;
while (curr != groupNext) {
ListNode tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
}
// 3. Connect previous segment to new reversed head
ListNode newGroupTail = groupPrev.next;
groupPrev.next = kth;
groupPrev = newGroupTail;
}
return dummy.next;
}Active Recall Checkpoint
In reverseKGroup, what is the role of initializing prev = groupNext inside the reversal loop?
Show answer & explanation
By initializing prev to groupNext (the node immediately after the k-group), the very first node reversed (the original head of the group, which becomes the new tail) automatically connects its next pointer to groupNext without needing an extra post-loop assignment.
Cost Model
Complexity & Trade-offs
When to use it
- Frequent local insertions, deletions, chain rewiring, and cycle analysis.
- Problems where contiguous storage or random access is unnecessary.
- In-place sequence transformations.
Common mistakes
- Losing the unread suffix by overwriting next too early.
- Failing to update head or tail after a boundary mutation.
- Dereferencing null or looping forever on a cycle.
Practice prompts
- Reproduce the worked In-place reversal example without looking at the trace.
- Change one input condition and explain whether the In-place reversal invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check