Reverse Linked List (LeetCode 206)
You get head, the first node of a singly linked list. Each node holds a value val and a pointer next to the node after it; the last node's next is None, and an empty list has head = None.
Turn the list around: the node that was last must come first, and every node must point to the one that used to come before it. Return the first node of the reversed list (None for an empty list, written []).
Follow-up: once you have one version, write the other one too, a loop and a recursive function.
Worked Examples
head = [1,2,3,4,5][5,4,3,2,1]5, the old last node, is the new head and 1 ends the list.head = [1,2][2,1]2 now points to 1, and 1 points to None.head = [][]⚖️Formal Constraints & Bounds
The number of nodes in the list is in the range
[0, 5000].-5000 <= Node.val <= 5000
Core Insight
Only the direction of each next pointer changes, so one forward walk that saves the next node, flips the current link and steps on reverses the whole list in place, without creating or copying a single node.
Real-World Scenario & Production Applications
Many systems keep history as a chain where each entry points to the one before it: an undo log, a version chain, a free list inside a memory allocator. To replay such a chain oldest-first you need the links pointing the other way. When the next pointer lives inside the object itself (an intrusive list, common in operating-system kernels), flipping the links in place does this without allocating a second list.
Step-by-Step Execution Trace Table
Input head = [1,2,3,4,5] (LeetCode Example 1). Before each step, prev heads the reversed part and curr heads the untouched part:
| Step | curr | nxt = curr.next | curr.next = prev | Reversed part (from prev) after the step | Untouched part (from curr) after the step |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 1 -> None | 1 -> None | 2 -> 3 -> 4 -> 5 -> None |
| 2 | 2 | 3 | 2 -> 1 | 2 -> 1 -> None | 3 -> 4 -> 5 -> None |
| 3 | 3 | 4 | 3 -> 2 | 3 -> 2 -> 1 -> None | 4 -> 5 -> None |
| 4 | 4 | 5 | 4 -> 3 | 4 -> 3 -> 2 -> 1 -> None | 5 -> None |
| 5 | 5 | None | 5 -> 4 | 5 -> 4 -> 3 -> 2 -> 1 -> None | empty (curr is None) |
| End | return prev: [5,4,3,2,1] |
| 1 | Only the direction of each `next` pointer changes: no node moves and no value is copied, so one forward walk can flip the links one at a time. |
| 2 | Keep two lists apart: `prev` heads the nodes already reversed (empty at first) and `curr` heads the nodes not touched yet; each step moves `curr` to the front of `prev`'s list. |
| 3 | `prev, curr = None, head`; `while curr:` save `nxt = curr.next`, flip `curr.next = prev`, then `prev = curr` and `curr = nxt`; after the loop `return prev`. |
| 4 | The trap: `nxt = curr.next` must run before `curr.next = prev`. The flip overwrites the only link to the rest of the list, so flipping first loses every node after `curr`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A singly linked list is a chain of nodes where each node knows only the node after it (next). To reverse it you don't move any node and you don't copy any value: you make every next point to the node that used to come before it. The list can only be walked forward, so you do it in one forward walk, carrying two pointers: prev, the head of the part already reversed, and curr, the first node not touched yet.
🏟️ The Analogy: Turning Around a Line of People Holding Shoulders
Picture a queue where everyone rests a hand on the shoulder of the person in front. To turn the whole line around, you go from the front to the back and ask each person to move their hand to the person behind them instead. Before someone lets go, you must note who they were holding, or you lose track of the rest of the line. That note is nxt.
🔑 Why It Works
Before every loop test, the nodes split into two separate lists: the reversed part starting at prev and the untouched part starting at curr. Each step moves exactly one node from the front of the untouched part to the front of the reversed part. The order of the four lines is the whole trick: curr.next = prev destroys the only link to the rest of the list, so nxt = curr.next must come first.
Flipping before saving:
nxt = curr.nextmust run beforecurr.next = prev. The flip overwrites the only link to the rest of the list, so flipping first loses every node aftercurr:[1,2,3]comes back as[1].Returning the wrong node: return
prev, notheadorcurr. When the loop endscurrisNone, and the oldheadis now the tail, pointing atNone.Stopping one node early: loop
while curr:, notwhile curr.next:. The shorter loop never flips the last node, and the empty list (headisNone) crashes onNone.next.Starting
prevathead: start withprev = None. The old head becomes the tail and must end pointing atNone; starting fromheadwithout clearinghead.nextleaves the first two nodes pointing at each other, a cycle.Copying instead of rewiring: reading the values into a Python list and building new nodes gives the right values but uses
O(N)extra memory; the four-line loop reuses the original nodes withO(1)extra space.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Reverse the list" and "return the reversed list": the nodes stay the same and only their order changes, and a singly linked list can only be walked forward. The need is to point every next the other way during one forward walk, in place: the Linked List Reversal tool.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Before each loop test, prev is the head of the nodes already reversed and curr is the head of the nodes not touched yet, and every node is in exactly one of the two lists. Each step moves one node, curr, from the front of the untouched part to the front of the reversed part.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Linked List Reversal. The nodes stay where they are; only each next pointer has to point the other way, so I walk the list once with two pointers. prev is the head of the part I've already reversed, starting as None, and curr is the first node I haven't touched. At each step I save curr.next in nxt, point curr.next back at prev, then move prev to curr and curr to nxt. Every node moves from the untouched part to the front of the reversed part exactly once, so when curr runs off the end, prev is the new head. The trap is the order of those lines: if I flip before saving nxt, I lose the rest of the list. That's
O(N)time andO(1)extra space, and no node is created.
Complexity & Mathematical Proof
O(N)
O(N): the while curr: loop runs once per node with constant work inside, and nothing else in the code depends on N.
O(1)
The code creates no node and no list: it only rewrites the next field that every node already has. The extra memory is three pointers, prev, curr and nxt, whatever the length of the list, so O(1). The returned list is the input's own nodes, so there is no separate output to count.
T = O(1) setup + N · O(1) per node = O(N)
Derivation Progression
O(1)
prev = None and curr = head run once.
N iterations
Each pass of while curr: ends with curr = nxt, one node forward, so the loop body runs exactly once per node.
O(1) per node
nxt = curr.next, curr.next = prev, prev = curr, curr = nxt: four pointer assignments, no inner loop.
O(N)
N iterations of constant work, plus the O(1) return prev.
Variable Definitions
Number of nodes in the list (0 to 5000)
Head of the part already reversed (None at the start)
First node not flipped yet (None once every node is done)
curr.next, saved before the flip overwrites it
Memory Architecture & Bounds
O(1) Iterative, no recursion (a recursive version would use an O(N) call stack)
O(1): three pointers, prev, curr and nxt; no node is created
None extra: the returned list is the input's own nodes, rewired
Boundary Best / Worst Cases
: an empty list never enters the loop
: every node is visited once
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "reverse the list", "return the reversed list". The nodes stay the same and only the order of the links changes, and a singly linked list can only be walked forward: Linked List Reversal, flipping each next during one walk.
nodes, values in . Any approach fits; the point is memory: copying the values costs extra, rewiring in place costs . A recursive version is also time but puts frames on the call stack.
At scale: a recursive reversal puts one stack frame per node, so a long list can overflow the call stack (Python's default limit is about 1000 frames), which the loop never does.
Core Algorithmic State Invariants
- Short Lists Need No Special Case
Because prev starts as None, an empty list skips the loop and returns None, and a one-node list runs it once, setting head.next = None (it already was) and returning head. The same four lines cover every length, so no if is needed before the loop.
- Where the Loop Stops Is Where the Segment Reconnects
In reverse_between, the counted loop stops with prev on the segment's new first node and curr on the first node after the segment. Those are exactly the two ends that before.next = prev and tail.next = curr need, so no second walk is needed to find them.
Reverse Linked List (LeetCode 206)
You get head, the first node of a singly linked list. Each node holds a value val and a pointer next to the node after it; the last node's next is None, and an empty list has head = None.
Turn the list around: the node that was last must come first, and every node must point to the one that used to come before it. Return the first node of the reversed list (None for an empty list, written []).
Follow-up: once you have one version, write the other one too, a loop and a recursive function.
Worked Examples
head = [1,2,3,4,5][5,4,3,2,1]5, the old last node, is the new head and 1 ends the list.head = [1,2][2,1]2 now points to 1, and 1 points to None.head = [][]⚖️Formal Constraints & Bounds
The number of nodes in the list is in the range
[0, 5000].-5000 <= Node.val <= 5000
Core Insight
Only the direction of each next pointer changes, so one forward walk that saves the next node, flips the current link and steps on reverses the whole list in place, without creating or copying a single node.
Real-World Scenario & Production Applications
Many systems keep history as a chain where each entry points to the one before it: an undo log, a version chain, a free list inside a memory allocator. To replay such a chain oldest-first you need the links pointing the other way. When the next pointer lives inside the object itself (an intrusive list, common in operating-system kernels), flipping the links in place does this without allocating a second list.
Step-by-Step Execution Trace Table
Input head = [1,2,3,4,5] (LeetCode Example 1). Before each step, prev heads the reversed part and curr heads the untouched part:
| Step | curr | nxt = curr.next | curr.next = prev | Reversed part (from prev) after the step | Untouched part (from curr) after the step |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 1 -> None | 1 -> None | 2 -> 3 -> 4 -> 5 -> None |
| 2 | 2 | 3 | 2 -> 1 | 2 -> 1 -> None | 3 -> 4 -> 5 -> None |
| 3 | 3 | 4 | 3 -> 2 | 3 -> 2 -> 1 -> None | 4 -> 5 -> None |
| 4 | 4 | 5 | 4 -> 3 | 4 -> 3 -> 2 -> 1 -> None | 5 -> None |
| 5 | 5 | None | 5 -> 4 | 5 -> 4 -> 3 -> 2 -> 1 -> None | empty (curr is None) |
| End | return prev: [5,4,3,2,1] |
| 1 | Only the direction of each `next` pointer changes: no node moves and no value is copied, so one forward walk can flip the links one at a time. |
| 2 | Keep two lists apart: `prev` heads the nodes already reversed (empty at first) and `curr` heads the nodes not touched yet; each step moves `curr` to the front of `prev`'s list. |
| 3 | `prev, curr = None, head`; `while curr:` save `nxt = curr.next`, flip `curr.next = prev`, then `prev = curr` and `curr = nxt`; after the loop `return prev`. |
| 4 | The trap: `nxt = curr.next` must run before `curr.next = prev`. The flip overwrites the only link to the rest of the list, so flipping first loses every node after `curr`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A singly linked list is a chain of nodes where each node knows only the node after it (next). To reverse it you don't move any node and you don't copy any value: you make every next point to the node that used to come before it. The list can only be walked forward, so you do it in one forward walk, carrying two pointers: prev, the head of the part already reversed, and curr, the first node not touched yet.
🏟️ The Analogy: Turning Around a Line of People Holding Shoulders
Picture a queue where everyone rests a hand on the shoulder of the person in front. To turn the whole line around, you go from the front to the back and ask each person to move their hand to the person behind them instead. Before someone lets go, you must note who they were holding, or you lose track of the rest of the line. That note is nxt.
🔑 Why It Works
Before every loop test, the nodes split into two separate lists: the reversed part starting at prev and the untouched part starting at curr. Each step moves exactly one node from the front of the untouched part to the front of the reversed part. The order of the four lines is the whole trick: curr.next = prev destroys the only link to the rest of the list, so nxt = curr.next must come first.
Flipping before saving:
nxt = curr.nextmust run beforecurr.next = prev. The flip overwrites the only link to the rest of the list, so flipping first loses every node aftercurr:[1,2,3]comes back as[1].Returning the wrong node: return
prev, notheadorcurr. When the loop endscurrisNone, and the oldheadis now the tail, pointing atNone.Stopping one node early: loop
while curr:, notwhile curr.next:. The shorter loop never flips the last node, and the empty list (headisNone) crashes onNone.next.Starting
prevathead: start withprev = None. The old head becomes the tail and must end pointing atNone; starting fromheadwithout clearinghead.nextleaves the first two nodes pointing at each other, a cycle.Copying instead of rewiring: reading the values into a Python list and building new nodes gives the right values but uses
O(N)extra memory; the four-line loop reuses the original nodes withO(1)extra space.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Reverse the list" and "return the reversed list": the nodes stay the same and only their order changes, and a singly linked list can only be walked forward. The need is to point every next the other way during one forward walk, in place: the Linked List Reversal tool.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Before each loop test, prev is the head of the nodes already reversed and curr is the head of the nodes not touched yet, and every node is in exactly one of the two lists. Each step moves one node, curr, from the front of the untouched part to the front of the reversed part.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Linked List Reversal. The nodes stay where they are; only each next pointer has to point the other way, so I walk the list once with two pointers. prev is the head of the part I've already reversed, starting as None, and curr is the first node I haven't touched. At each step I save curr.next in nxt, point curr.next back at prev, then move prev to curr and curr to nxt. Every node moves from the untouched part to the front of the reversed part exactly once, so when curr runs off the end, prev is the new head. The trap is the order of those lines: if I flip before saving nxt, I lose the rest of the list. That's
O(N)time andO(1)extra space, and no node is created.
Complexity & Mathematical Proof
O(N)
O(N): the while curr: loop runs once per node with constant work inside, and nothing else in the code depends on N.
O(1)
The code creates no node and no list: it only rewrites the next field that every node already has. The extra memory is three pointers, prev, curr and nxt, whatever the length of the list, so O(1). The returned list is the input's own nodes, so there is no separate output to count.
T = O(1) setup + N · O(1) per node = O(N)
Derivation Progression
O(1)
prev = None and curr = head run once.
N iterations
Each pass of while curr: ends with curr = nxt, one node forward, so the loop body runs exactly once per node.
O(1) per node
nxt = curr.next, curr.next = prev, prev = curr, curr = nxt: four pointer assignments, no inner loop.
O(N)
N iterations of constant work, plus the O(1) return prev.
Variable Definitions
Number of nodes in the list (0 to 5000)
Head of the part already reversed (None at the start)
First node not flipped yet (None once every node is done)
curr.next, saved before the flip overwrites it
Memory Architecture & Bounds
O(1) Iterative, no recursion (a recursive version would use an O(N) call stack)
O(1): three pointers, prev, curr and nxt; no node is created
None extra: the returned list is the input's own nodes, rewired
Boundary Best / Worst Cases
: an empty list never enters the loop
: every node is visited once
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "reverse the list", "return the reversed list". The nodes stay the same and only the order of the links changes, and a singly linked list can only be walked forward: Linked List Reversal, flipping each next during one walk.
nodes, values in . Any approach fits; the point is memory: copying the values costs extra, rewiring in place costs . A recursive version is also time but puts frames on the call stack.
At scale: a recursive reversal puts one stack frame per node, so a long list can overflow the call stack (Python's default limit is about 1000 frames), which the loop never does.
Core Algorithmic State Invariants
- Short Lists Need No Special Case
Because prev starts as None, an empty list skips the loop and returns None, and a one-node list runs it once, setting head.next = None (it already was) and returning head. The same four lines cover every length, so no if is needed before the loop.
- Where the Loop Stops Is Where the Segment Reconnects
In reverse_between, the counted loop stops with prev on the segment's new first node and curr on the first node after the segment. Those are exactly the two ends that before.next = prev and tail.next = curr need, so no second walk is needed to find them.