In-place linked list reversal
Rewiring next pointers with a prev/curr/next triple reverses a singly linked list, or any sub-range of one, in O(n) time and O(1) space.
In-place linked list reversal
The player loads from youtube-nocookie.com when you press play. Nothing reaches YouTube before that.
Not started
What you'll learn
- Reversing a singly linked list in place means walking it once with three pointers — prev, curr, and a saved next — and on each step rewiring curr.next to point backward to prev before advancing all three forward, never allocating a new node.
- Saving next = curr.next before overwriting curr.next is the step that makes the whole thing work: once you rewrite curr.next to point to prev, you've destroyed the only link to the rest of the list, so you must capture that link first.
- After the loop finishes, prev — not curr — is the new head of the reversed list, because curr has walked one step past the last real node (it ends at null) while prev is left sitting on the final node that was processed, which is now first.
- Reversing a sub-range [left, right] instead of the whole list only changes the bookkeeping at the edges: walk to the node just before left, run the same prev/curr/next reversal loop for exactly (right - left + 1) steps, then reconnect the node before the range to the new sub-range head and the sub-range's original head to whatever came after right.
- Reversing in groups of k is the sub-range reversal applied repeatedly: reverse the first k nodes, recursively or iteratively reverse the next k, and stitch each group's new head to the previous group's new tail, with the one subtlety that a final group shorter than k is usually left unreversed.
- All of these variants stay O(1) extra space because the reversal never needs a stack, array, or second list — the rewiring happens directly on the existing nodes, which is the entire point of doing it in place.
Why “in place” matters here
The naive way to reverse a linked list is to walk it, collect every node’s value into
an array, then rebuild the list (or a new one) in reverse order. That works but costs
O(n) extra space. The in-place technique reverses the list by rewiring the existing
next pointers directly on the existing nodes — no new nodes, no array, O(1) extra
space beyond a few pointer variables. The mechanism is always the same three-pointer
dance: prev, curr, and a temporary next.
The core loop, worked through
Start with prev = null and curr = head. At each step:
- Save
next = curr.next(before you destroy it). - Rewire:
curr.next = prev. - Advance both:
prev = curr,curr = next.
Trace it on 1 -> 2 -> 3 -> null. Initial: prev = null, curr = node(1).
- Step 1:
next = node(2). Rewire:node(1).next = null. Advance:prev = node(1),curr = node(2). List so far:1 -> null, with2 -> 3 -> nullstill dangling off to the side viacurr. - Step 2:
next = node(3). Rewire:node(2).next = node(1). Advance:prev = node(2),curr = node(3). - Step 3:
next = null. Rewire:node(3).next = node(2). Advance:prev = node(3),curr = null.
Loop ends (curr is null). prev now points at node(3), and following .next
pointers from there gives 3 -> 2 -> 1 -> null — the fully reversed list. prev, not
curr, is the new head, because curr’s final advance walked it one step past the
real last node into null, while prev was left holding the last node actually
processed.
Reversing only a sub-range
“Reverse the list between position left and right” (LeetCode 92) needs the same
loop, applied only to that slice, plus careful bookkeeping at the two boundaries.
First, walk a pointer to the node just before left — call it beforeRange — since
that node’s next pointer will need to be redirected after the reversal. Then run the
exact prev/curr/next loop above, but only for right - left + 1 steps, starting with
curr at the node originally at position left.
When it finishes, prev is the new head of the reversed sub-range (originally the
node at right). The original node at left is now the tail of the reversed
segment, and curr — which has walked just past the range — is sitting on whatever
comes after it. Stitch the two seams back together: beforeRange.next = prev connects
the part before the range to the new sub-range head, and the sub-range’s original
head’s .next is pointed at wherever curr landed. Nothing outside [left, right] is
ever touched — only the pointers at those two seams change.
Generalizing to k-group reversal
“Reverse Nodes in k-Group” (LeetCode 25) applies sub-range reversal repeatedly: reverse
the first k nodes using the loop above, then treat the rest of the list as a fresh
problem and reverse its first k nodes, and so on, stitching each group’s new head to
the previous group’s new tail as you go. The one added wrinkle is a lookahead check:
before reversing a group, walk ahead k nodes to confirm a full group actually exists;
if fewer than k nodes remain, that trailing partial group is left in its original
order rather than reversed. Every group reversal is still the identical prev/curr/next
mechanism — k-group reversal is sub-range reversal applied in a loop, not a new
algorithm.
Why this is the right tool
Any time a linked-list problem asks for a structural change (reverse all, reverse a window, reverse groups, even some palindrome-checking and reordering problems) rather than a value change, this three-pointer rewiring is the mechanism to reach for: it’s always O(n) time, always O(1) extra space, and the only real design decision is where the reversal loop starts, stops, and how its boundaries get reconnected.
Check yourself
Why must you save curr.next into a temporary variable before setting curr.next = prev, rather than doing the reassignment first and reading curr.next afterward?
curr.next is the only remaining link to the rest of the unprocessed list; once you overwrite it to point backward at prev, that forward link is gone, so if you hadn't saved it first you'd have no way to advance to the next node — you'd have orphaned the remainder of the list.
After the full-list reversal loop ends (curr has become null), why is prev the new head instead of curr?
The loop's last useful action was processing the final real node and setting prev to point at it; curr only advances past the end to null afterward, as the loop's termination check, so curr holds no useful node reference at the end, while prev still references the actual last-processed node, which is now logically first.
When reversing only a sub-range [left, right] of a linked list, why do you need a reference to the node just before index left, even though that node itself isn't part of the range being reversed?
After reversing the sub-range, that node-before-left is the one whose next pointer must be updated to point at the new head of the reversed sub-range (which was originally the node at index right); without holding onto it beforehand, you'd have no way to reconnect the reversed segment back into the rest of the list, since the sub-range's original entry point no longer leads anywhere useful.
Go deeper
Notes
Notes are saved to your account.
Everything else on this page works without one — progress and bookmarks keep themselves in this browser and come with you when you sign in. Notes are the one thing worth not trusting to a browser you might clear.
Your notes could not be loaded.