Reverse a Linked List is the classic pointer-juggling problem. It teaches you to rewire a chain of nodes in place — one link at a time — without losing the rest of the list. The whole trick is keeping three pointers in your head: where you were, where you are, and where you are about to go.
Problem. Given the head of a singly linked list, reverse the list and return the new head. A
singly linked list only has next pointers, so each node knows the one after it, never the one before.
Example: 1 → 2 → 3 → 4 → returns 4 → 3 → 2 → 1.
The idea
Each node has a single next arrow pointing forward. To reverse the list, we walk through it and flip every arrow to point backwards instead. The catch: the moment you flip a node's next to point at the previous node, you have erased the link to the rest of the list. So before you flip, you must save the next node.
That gives us three pointers:
prev— the part already reversed (starts atNone).curr— the node we are flipping right now (starts athead).nxt— a temporary handle oncurr.next, saved before we overwrite it.
We repeat those four moves until curr walks off the end (curr is None). At that point prev is sitting on the old last node — which is now the new head — so we return prev.
Walk through it
Step through the animation. The curr pointer scans left to right. On each node we save the next node, then the forward arrow disappears and a curved arrow appears pointing back to prev. By the end every arrow has flipped, curr has fallen off the end, and prev rests on node 4 — the new head.
Pseudocode
prev = None
curr = head
while curr is not None:
nxt = curr.next # save the rest of the list
curr.next = prev # flip this node's arrow backwards
prev = curr # prev moves up to curr
curr = nxt # curr moves to the saved next node
return prev # prev is the new headThe order matters: save nxt first, then flip, then advance. If you flip before saving, curr.next already points at prev and you can never reach the rest of the list.
The Python solution
def reverse_list(head):
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prevprevbegins asNonebecause the original head will become the new tail, and a tail'snextisNone.while curr:keeps going as long as there is a node to process; it stops whencurrbecomesNone.- Line 5 (
nxt = curr.next) is the safety move — it stashes the rest of the list before we overwrite the link. - Line 6 (
curr.next = prev) is the actual reversal: this node now points backwards. - The last two lines slide the window forward:
prevtakescurr's spot, andcurrjumps to the savednxt. - When the loop ends,
prevholds the last node we flipped — the new head — so we return it.
Complexity
| Case | Time | Notes |
|---|---|---|
| Iterative (this solution) | O(n) (moderate) | one pass, flip each link once |
| Recursive | O(n) (moderate) | same work, but O(n) call stack |
O(1) (fast)The iterative version uses only three pointers no matter how long the list is — that is O(1) extra space. The recursive version is elegant but pays O(n) space for the call stack, which can overflow on a very long list.
When this pattern shows up
The "three pointers — save, flip, advance" move is the backbone of nearly every in-place linked-list
problem: reverse a sublist, reverse in groups of k, detect/return a cycle, swap pairs. Whenever you
must rewire next pointers without extra memory, picture prev / curr / nxt walking the list.
Never flip curr.next before saving it. curr.next = prev destroys the only reference to the rest of
the list, so you must grab nxt = curr.next on the line above — otherwise the remaining nodes are lost.
Practice
We are reversing 1 → 2 → 3 → 4. After we finish processing node 2 (flip its link and advance), what are prev and curr pointing to?
1. Why do we save nxt = curr.next before flipping the link?
2. What should prev be initialized to?
3. When the loop ends, what does the function return?
4. What is the extra space used by the iterative solution?