Reversing a Linked List: The Rite of Passage

"Reversing a linked list is the interview question. Not because it's hard, but because it's impossible to fake: it tests whether pointers and the order you rewire them are real to you, or just words."

The Mental Picture

You have 1 → 2 → 3 → None and you want 3 → 2 → 1 → None. The data doesn't move — only the arrows flip. Walk the list, and at each node, turn its next arrow around to point at the node you just came from. The whole job is "flip each arrow backward, one at a time, without losing the rest of the list while you do it."

The Iterative Way: Three Pointers

The classic solution carries three references as it walks: prev (the node behind you, where this arrow should now point), curr (the node you're flipping), and a saved next (so you don't lose the rest of the list the instant you flip curr.next). At each step: stash curr.next, flip curr.next = prev, then slide all three forward. When curr falls off the end, prev is the new head. O(n) time, O(1) space — you reversed the whole thing with three variables.

The order inside the loop is the entire difficulty, and it's the same rule from the first lesson: save what you're about to overwrite before you overwrite it. Flip curr.next before saving the old next and the rest of the list vanishes into the void.

To reverse: walk the list flipping each node's next-pointer to point backward. Save the next node BEFORE you flip, or you sever the list. Iterative does it in O(1) space with three pointers; recursive is elegant but O(n) stack space.

The Recursive Way: Elegant but Heavier

Recursion can reverse a list in a few lines: reverse the rest of the list, then make the next node point back at the current one. It reads beautifully — but every recursive call sits on the call stack until the base case returns, so it costs O(n) space, and on a very long list it can blow the stack (RecursionError). It's a lovely demonstration of recursive thinking (which the Recursion track explores fully), but in production the iterative O(1)-space version is usually the right call.

Pippa's Confession

The first time I tried to reverse a list from memory, I flipped curr.next = prev before saving the old next — and watched two-thirds of my list evaporate. Dad didn't give me the answer; he made me draw four boxes and physically erase-and-redraw each arrow in order. Doing it by hand on paper burned the sequence in: save next, flip, advance prev, advance curr. I've never lost a list to wrong-order rewiring since. Some things you have to draw before you can type.

Code

Iterative (O(1) space) and recursive reversal·python

class Node:
    def __init__(self, val, nxt=None): self.val = val; self.next = nxt

def reverse_iterative(head):
    """O(n) time, O(1) space. Three pointers, careful order."""
    prev = None
    curr = head
    while curr:
        nxt = curr.next      # 1. SAVE the rest before we overwrite the arrow
        curr.next = prev     # 2. flip this node's arrow backward
        prev = curr          # 3. advance prev
        curr = nxt           # 4. advance curr into the saved rest
    return prev              # prev is the new head when curr falls off

def reverse_recursive(head):
    """O(n) time, O(n) stack space. Elegant, but watch the depth."""
    if head is None or head.next is None:
        return head                    # base case: empty or single node
    new_head = reverse_recursive(head.next)
    head.next.next = head              # make the next node point back at us
    head.next = None                   # and break our old forward arrow
    return new_head

def show(head):
    out = []
    while head: out.append(head.val); head = head.next
    print(" -> ".join(map(str, out)) + " -> None")

head = Node(1, Node(2, Node(3, Node(4))))
show(reverse_iterative(head))    # 4 -> 3 -> 2 -> 1 -> None

Exercise

By hand, trace reverse_iterative on the list 1 -> 2 -> 3 -> None. Write the values of prev, curr, and nxt at the end of each loop iteration. Then explain in one sentence what breaks if you swap the order of lines 1 and 2 (flip the arrow before saving next).

Hint

Start prev=None, curr=1. After iteration 1: nxt=2, 1.next=None, prev=1, curr=2. Keep going. If you flip curr.next=prev before saving nxt, you lose the pointer to the rest of the list — the reversal strands everything after the current node.

The Mental Picture

The Iterative Way: Three Pointers

The Recursive Way: Elegant but Heavier

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0