Reverse Linked List
Turn 1 → 2 → 3 into 3 → 2 → 1 by flipping every arrow, using three pointers (or recursion).
- Reversing a linked list
- Pointer rewiring
- Recursion
Before this, know: What a linked list is (see the week 4 overview), Following node.next in a loop
You get head, the first node of a singly linked list: a chain of nodes where
each node holds a value (val) and an arrow to the next node (next). The last
node’s next is null (None in Python), meaning “nothing after me”. Reverse
the list and return the new head.
The rules that matter:
- The list can be empty (
headis null) or have one node. Both are their own reverse. - Up to 5,000 nodes. We should change the existing nodes’ arrows, not build a new list.
Reversing means: every arrow A → B becomes B → A. Walk the list once, and at
each node point its arrow backwards, at the node we just came from. That
needs three pointers (a pointer here is just a variable that holds a node):
prev: the node behind us (the start of the part already reversed),curr: the node we’re flipping now,next: the node aftercurr, saved before we flip, because flippingcurr.nextdestroys our only link to the rest of the list.
Pause and think
Node 2’s only arrow pointed at 3. We just overwrote it to point at 1. Nothing else
points at 3, so we can never reach 3 again: the rest of the list is lost.
That’s why the very first move in the loop is next = curr.next.
The simplest idea doesn’t touch the arrows at all: walk the list and copy every
value into an array, then walk it again and write the values back, last one
first. pop() removes and returns the last item of an array, which hands the
values back in reverse.
Copy the values out, write them back reversed
head = [1, 2, 3, 4]
- node
- 1node
- 10
- Copying this node
- Value rewritten
- Done
Pass 1: copy node 1's value into the array. The array now holds [1].
Which line is running?
function reverseList(head) { const values = []; let node = head; while (node !== null) { // pass 1: copy every value outRunning now: values.push(node.val); node = node.next; } node = head; while (node !== null) { // pass 2: write them back, last value first node.val = values.pop(); node = node.next; } return head;}Copy values, write them back reversed
function reverseList(head) { const values = []; let node = head; while (node !== null) { // pass 1: copy every value out values.push(node.val); node = node.next; } node = head; while (node !== null) { // pass 2: write them back, last value first node.val = values.pop(); node = node.next; } return head;}def reverse_list(head): values = [] node = head while node is not None: # pass 1: copy every value out values.append(node.val) node = node.next node = head while node is not None: # pass 2: write them back, last value first node.val = values.pop() node = node.next return headIt’s O(n) time, which is fine, but it needs an extra array as long as the list: 5,000 nodes, 5,000 extra slots. It also changes the values, not the list. In real code nodes often carry more than a number (or other code holds references to them), and an interviewer will ask you to reverse the links. We can do that with three variables and no array.
Pattern
Reversing a linked list
Use it when: you need a list (or part of one) backwards, in place, without extra memory.
Signal words
- “reverse the list”
- “reverse between”
- “palindrome linked list”
- “reorder”
- “in place”
prev = null(the reversed part is empty) andcurr = head.- While
currisn’t null: - Save
next = curr.next. - Flip:
curr.next = prev. - Step
prev = curr, thencurr = next. - When the loop ends, return
prev: it’s the old tail, now the head.
Watch the arrows: each flipped arrow curves back underneath the row. Grey nodes
are the part already reversed (prev’s list). The amber node is the saved next,
our lifeline to the rest of the list.
Iterative: prev, curr, next
head = [1, 2, 3, 4]
- prev
- null
- curr
- 1node
- curr (being flipped)
- next (saved)
- Already reversed (prev's list)
- Arrow just flipped
- Reversed list
We will flip every arrow so it points backwards. prev holds the part we have already reversed. At the start that part is empty, so prev = null.
Which line is running?
function reverseList(head) {Running now: let prev = null; // the reversed part (empty at first) let curr = head; // the node we are flipping now while (curr !== null) { const next = curr.next; // 1. save the rest of the list curr.next = prev; // 2. flip this arrow backwards prev = curr; // 3. step prev forward curr = next; // 4. step curr forward } return prev; // the old tail is the new head}Recursion means a function calling itself on a smaller version of the same
problem. Here: “to reverse the list starting at head, first reverse everything
after head, then hang head on the end.”
The trick is to trust that reverseList(head.next) works (like trusting a
helper), then fix up just one arrow. When the recursive call returns, head.next
still points at its old neighbour, which is now the tail of the reversed part.
So head.next.next = head hangs head after it, and head.next = null makes
head the new end.
Every call that hasn’t finished waits on the call stack (a pile of paused function calls; the newest is on top). Watch it grow down the list, then shrink as each call fixes its arrow.
Recursive, with the call stack
head = [1, 2, 3]
- reverseList(1)head = 1
- head
- 1node
- newHead
- null
- This call's head
- head.next
- Arrow just changed
- newHead
Call reverseList(1). First question: is the list empty or a single node?
Which line is running?
function reverseList(head) {Running now: if (head === null || head.next === null) { return head; // 0 or 1 node: already reversed } const newHead = reverseList(head.next); // reverse everything after head head.next.next = head; // the node after head points back at head head.next = null; // head is now the tail of the reversed part return newHead;}Recursive
function reverseList(head) { if (head === null || head.next === null) { return head; // 0 or 1 node: already reversed } const newHead = reverseList(head.next); // reverse everything after head head.next.next = head; // the node after head points back at head head.next = null; // head is now the tail of the reversed part return newHead;}def reverse_list(head): if head is None or head.next is None: return head # 0 or 1 node: already reversed new_head = reverse_list(head.next) # reverse everything after head head.next.next = head # the node after head points back at head head.next = None # head is now the tail of the reversed part return new_headIterative (the one to use)
function reverseList(head) { let prev = null; // the reversed part (empty at first) let curr = head; // the node we are flipping now while (curr !== null) { const next = curr.next; // 1. save the rest of the list curr.next = prev; // 2. flip this arrow backwards prev = curr; // 3. step prev forward curr = next; // 4. step curr forward } return prev; // the old tail is the new head}def reverse_list(head): prev = None # the reversed part (empty at first) curr = head # the node we are flipping now while curr is not None: nxt = curr.next # 1. save the rest of the list curr.next = prev # 2. flip this arrow backwards prev = curr # 3. step prev forward curr = nxt # 4. step curr forward return prev # the old tail is the new headThe line numbers match in both languages. On LeetCode this sits inside
var reverseList = function(head) {...} (JavaScript) or class Solution with
def reverseList(self, head) (Python), and LeetCode defines ListNode for you.
- Line 2:
prevstarts asnull. The first node will become the last node, and the last node must point to null, so null is exactly what it should point at after its flip. - Line 3:
currstarts at the head. - Line 4: keep going while there’s a node to flip. An empty list skips the loop entirely.
- Line 5: save the rest of the list. Python names it
nxtbecausenextis a built-in Python function and shadowing it is bad style. - Line 6: the actual reversal: this node now points backwards.
- Lines 7–8: move both pointers one node forward. Order matters:
prevmust takecurr’s value beforecurrmoves on. - Line 10 (JS) / 9 (Py):
curris null, soprevis the last node we flipped, the new head. Returningheadhere is a classic bug: the old head is now the tail.
For the recursive version: line 2 is the base case (empty or one node is
already reversed), JS 5 / Py 4 reverses the rest, JS 6–7 / Py 5–6 fix the
two arrows, and the same newHead is passed all the way back up.
head = [1, 2, 3, 4], one row per trip around the loop (iterative):
| curr | next (saved) | flip | prev after | reversed part | rest |
|---|---|---|---|---|---|
| 1 | 2 | 1 → null | 1 | 1 | 2 → 3 → 4 |
| 2 | 3 | 2 → 1 | 2 | 2 → 1 | 3 → 4 |
| 3 | 4 | 3 → 2 | 3 | 3 → 2 → 1 | 4 |
| 4 | null | 4 → 3 | 4 | 4 → 3 → 2 → 1 | (empty) |
| null | — | — | 4 | return prev = 4 | — |
At every row the list is split into two healthy lists: the reversed part (starting
at prev) and the rest (starting at next). Nothing is ever lost.
Copy values out and back
Time
O(n)
Two passes over the n nodes.
Space
O(n)
An extra array holding every value.
Iterative prev / curr / next
Time
O(n)
One pass; each node is flipped once.
Space
O(1)
Three pointer variables, whatever the list's length.
Recursive
Time
O(n)
One call per node.
Space
O(n)
The call stack holds one paused call per node: 5,000 nodes, 5,000 frames.
What to say out loud:
- “I’ll reverse the links in place with three pointers: prev, curr and next.”
- “Save next first, flip curr.next to prev, then advance both.”
- “O(n) time, O(1) space. The recursive version is O(n) space because of the call stack.”
- Draw three boxes and walk one iteration before writing code.
Likely follow-ups:
- “Reverse only positions left to right.” (Reverse Linked List II, LeetCode 92)
Walk to the node before
left, reverse the nextright − left + 1nodes the same way, then reconnect both ends. - “Can you do it recursively?” Approach 3 above.
Related problems:
- Reorder List: reversing the second half is one of its three phases.
- Palindrome Linked List (LeetCode 234): find the middle, reverse the second half, compare.
- The full template and more is in the week 4 overview.