Reverse Linked List
Re-point each node's next to the node behind it as you walk.
Pointer Reversal
Problem
Given the head of a singly linked list, change the links so the list is ordered in reverse. Return the node that becomes the new head after the reversal. The original nodes must be reused rather than copied into a separate list.
Examples
Input: head = [1,2,3,4]
Output: [4,3,2,1]
Input: head = [7,8]
Output: [8,7]
The Goal
Reverse a singly linked list and return its new head. Change the next links. Don't copy the nodes or swap their values.
For 1 → 2 → 3 → 4, every arrow turns around: 4 → 3 → 2 → 1. Node 1, the old head, now points to None, and node 4 is the new head.
The hard part is order. Once you overwrite a node's next, the rest of the list is gone unless you saved it first.
Turn the arrows around
Each node's next points to the node that came before it. The old head points to None.
Change links, not values.
Key Idea: Two Halves and a Saved Link
Walk the list with current. Every node behind it is already reversed, and prev is the head of that part. Every node from current on is untouched.
Each step moves one node from the untouched half to the front of the reversed half. Before you flip current.next, save it in temp. That saved link is the only way to reach the rest of the list.
The old current.next, saved before the flip.
4 is saved before 3's link turns back to 2.
The Algorithm
Save the next node, flip the link, then move both pointers up.
def reverse_list(head):
prev, current = None, head
while current:
temp = current.next
current.next = prev
prev = current
current = temp
return prevWhen current reaches None, every link is flipped and prev is the new head. Return prev, not head: the old head is now the last node.
| Approach | Time | Extra space | Trade-off |
|---|---|---|---|
| Flip links in a loop | O(n) | O(1) | One pass, the same nodes |
| Recursion | O(n) | O(n) | The call stack grows with the list |
| Copy the values out and back | O(n) | O(n) | Reverses the values, not the links |
Walkthrough
Run it on 1 → 2 → 3 → 4.
Each node takes four steps on the stage: temp saves the next node, the link turns back, prev moves up, and current moves on. Watch the first flip. Node 1 points to None, and only temp still reaches node 2.
On the last node, temp saves None. After the flip and the two moves, current is None and prev is node 4, the head of 4 → 3 → 2 → 1.
Checkpoint · predict the next step
Step 6 of 18 on the stage: Save current.next in temp: 3. Flipping current's link would lose it otherwise.
prev on 1 · current on 2 · temp on 3 · links 1→None, 2→3, 3→4, 4→None
Pitfalls
- Save
current.nextbefore you overwrite it. Flip first, and the rest of the list is lost. - Return
prev.headis now the last node. - An empty list returns
None: the loop never runs. - A single node is its own reversal. Its
nextstaysNone. - Try Break it with repeated values. The links turn the same way, whatever the nodes hold.
With current on node 1 of 1 → 2 → 3, which line has to run first?
Complexity
Each node is visited once and gets one flip, so time is O(n).
Only three pointers are kept, prev, current and temp, however long the list is. Extra space is O(1). A recursive version is shorter to write but uses O(n) space on the call stack.
One pass, three pointers
- Visit each nodeOnce each.dominantO(n)
- Flip a linkPer node.O(1)
- prev, current, tempThree pointers, whatever the length.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
One pass, and nothing new is built.
In short
Keep prev = null and iterate. For each node, remember its next, flip its pointer to prev, then advance prev and current forward. When you fall off the end, prev is the new head. It's an in-place pointer reversal in one pass.
Common mistake
Losing the rest of the list by overwriting node.next before saving it in a temp.