Linked Lists5 min read

Reversing a Linked List

Flip the entire chain so the last node becomes first — iteratively or recursively
time: \(O(n)\)space: \(O(1)\) iterative / \(O(n)\) recursive

Imagine your treasure-hunt chain: clue 1 → clue 2 → clue 3 → treasure. Now flip it: treasure → clue 3 → clue 2 → clue 1. Every arrow that pointed forward now points backward. The last node becomes the new head.

Reversing a linked list is one of the most fundamental linked-list operations, and it's a staple interview question because it tests whether you truly understand pointer manipulation. The good news: it's simpler than it looks.

The iterative approach

Walk through the list once, redirecting each pointer as you go. You need three variables:

  • prev — the previously processed node (starts as null)
  • curr — the node you're currently processing (starts at head)
  • next — a temporary save of curr.next before you overwrite it

At each step:

  1. Save next = curr.next (so you don't lose the rest of the chain)
  2. Flip the pointer: curr.next = prev
  3. Advance: prev = curr, curr = next

When curr is null, you've processed every node. prev is now the new head.

◈ Watch list reversal

← → arrow keys to step · click elements to interact

Reverse a Linked List (Iterative)

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


def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev  # new head


def build(vals):
    dummy = Node(0); cur = dummy
    for v in vals: cur.next = Node(v); cur = cur.next
    return dummy.next


def to_list(head):
    res=[]; cur=head
    while cur: res.append(cur.val); cur=cur.next
    return res


head = build([1, 2, 3, 4, 5])
head = reverse(head)
print(to_list(head))  # [5, 4, 3, 2, 1]
Output
[5, 4, 3, 2, 1]
Note: The classic mistake: forgetting to save next = curr.next before overwriting curr.next. Once you flip the pointer, you've lost the reference to the rest of the list. Always save the forward reference first.

Walking through an example

List: 1 → 2 → 3 → 4 → null

Initial state: prev = null, curr = 1

  • Step 1: save next=2, flip 1→null, advance. State: prev=1, curr=2
  • Step 2: save next=3, flip 2→1, advance. State: prev=2, curr=3
  • Step 3: save next=4, flip 3→2, advance. State: prev=3, curr=4
  • Step 4: save next=null, flip 4→3, advance. State: prev=4, curr=null

curr is null — done. New head: 4 → 3 → 2 → 1 → null

The recursive approach

The recursive solution is more elegant to write but costs \(O(n)\) stack space — one stack frame per node:

pseudocode
1
2
3
4
5
6
7
function reverse(node):
    if node == null or node.next == null:
        return node  # base case: new head
    newHead = reverse(node.next)
    node.next.next = node  # make next node point back to current
    node.next = null       # current node's next becomes null
    return newHead

The recursion goes all the way to the last node, then unwinds. On the way back up, each call makes its child point back at itself and sets its own forward pointer to null. The last node (base case) becomes the new head and is returned unchanged up through all the recursive calls.

Iterative vs. Recursive — which to choose?

  • Iterative: \(O(1)\) space — preferred in production and for very long lists (no stack overflow risk)
  • Recursive: \(O(n)\) stack space — cleaner to read and reason about, but risky for lists with millions of nodes

Both run in \(O(n)\) time. In interviews, demonstrating both and explaining the tradeoff is the ideal answer.

Variations

The same pointer-manipulation logic powers more complex operations:

  • Reverse a sublist — reverse only nodes from position m to n
  • Reverse in k-groups — reverse every k nodes in chunks
  • Palindrome check — reverse the second half and compare to the first

Complexity

Iterative reversal — time
One pass through the list
Linear \(O(n)\)
Iterative reversal — space
Only three pointer variables
Constant \(O(1)\)
Recursive reversal — time
One recursive call per node
Linear \(O(n)\)
Recursive reversal — space
Call stack depth equals list length
Linear \(O(n)\)

Reverse a Linked List (Recursive)

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


def reverse_recursive(head):
    if not head or not head.next: return head
    new_head = reverse_recursive(head.next)
    head.next.next = head  # reverse the link
    head.next = None
    return new_head


def build(vals):
    dummy = Node(0); cur = dummy
    for v in vals: cur.next = Node(v); cur = cur.next
    return dummy.next


def to_list(head):
    res=[]; cur=head
    while cur: res.append(cur.val); cur=cur.next
    return res


head = build([1, 2, 3, 4, 5])
head = reverse_recursive(head)
print(to_list(head))  # [5, 4, 3, 2, 1]
Output
[5, 4, 3, 2, 1]
Challenge

Quick check

In the iterative reversal algorithm, why must you save next = curr.next before flipping the pointer?

Continue reading