Linked List Reversal

Reversing a singly linked list is the canonical linked-list interview question. Given a head pointer, return a new head pointing to the same nodes in reverse order. The textbook iterative solution uses three pointers — prev, curr, next — and rewires each node’s next to point backward, taking O(n) time and O(1) space. The recursive solution is one-line elegant but uses O(n) space on the call stack. Both are worth knowing; the iterative version is what you should reach for in an interview because of its space efficiency. This note also covers the two important variants — reverse a sublist between positions m and n (LC 92) and reverse in groups of k (LC 25) — both of which extend the same three-pointer technique with bookkeeping for sublist boundaries.

1. Intuition — Walking and Flipping the Arrows

A singly linked list 1 → 2 → 3 → 4 → null is a sequence of arrows. To reverse it, we want every arrow to flip direction: null ← 1 ← 2 ← 3 ← 4, with the original tail (4) now the head.

Imagine you walk down the list from head to tail. As you stand at each node, you flip its arrow to point backward — at the node you came from. To do that flip, you need three pieces of information:

• curr — the node you’re standing on, the one whose arrow you’re about to flip.
• prev — the node behind you, the one curr.next will now point at.
• next — what curr.next currently points at, so you don’t lose it when you overwrite. Without saving this, the moment you set curr.next = prev, the rest of the list is unreachable and lost forever.

The three pointers are the entire technique. Walk: save next, flip curr.next to prev, advance prev = curr and curr = next. Repeat until curr == null. The new head is prev.

2. Tiny Worked Example — Reversing 1 → 2 → 3 → null

I’ll trace each iteration of the iterative algorithm with ASCII pictures of pointer state. The list is initially:

  head
   ↓
  [1] → [2] → [3] → null

Set prev = null, curr = head.

Initial:

  prev = null    curr = [1]
                  ↓
  null    [1] → [2] → [3] → null

         (curr.next still points at [2])

Iteration 1

  Step A — save next:
    next = curr.next = [2]

  Step B — flip arrow:
    curr.next := prev      i.e., [1].next := null

  Step C — advance:
    prev := curr           prev = [1]
    curr := next           curr = [2]

  State after iteration 1:

  null ← [1]      [2] → [3] → null
          ↑       ↑
        prev    curr

Notice [1] now points to null (we flipped its arrow); [2] and [3] are untouched, still pointing forward, and we’ve moved one step down the list.

Iteration 2

  Step A — save next:
    next = curr.next = [3]

  Step B — flip arrow:
    [2].next := prev = [1]

  Step C — advance:
    prev := [2]
    curr := [3]

  State after iteration 2:

  null ← [1] ← [2]      [3] → null
                 ↑       ↑
               prev    curr

[2] now points back to [1]. The reversed-prefix is [2] → [1] → null. The unprocessed-suffix is [3] → null.

Iteration 3

  Step A — save next:
    next = curr.next = null

  Step B — flip arrow:
    [3].next := prev = [2]

  Step C — advance:
    prev := [3]
    curr := null

  State after iteration 3:

  null ← [1] ← [2] ← [3]      null
                       ↑       ↑
                     prev    curr (terminates loop)

curr == null, loop ends. prev is [3], the new head. Return prev.

Final list: [3] → [2] → [1] → null. Three iterations for a 3-node list — O(n) work overall, three pointers in memory — O(1) space. ✓

Loop Invariant

After iteration k:

• The first k nodes have been reversed; prev points to their new head.
• curr points to the (k+1)-th original node — the start of the unprocessed suffix.
• The unprocessed suffix is intact (still pointing forward, in original order).

This invariant is what you assert during a whiteboard explanation; it makes the correctness obvious.

3. Pseudocode — Iterative

reverse(head):
    prev := null
    curr := head
    while curr != null:
        next := curr.next       # save
        curr.next := prev        # flip
        prev := curr             # advance prev
        curr := next             # advance curr
    return prev                  # new head

Five lines. Every line is essential. The order of the four assignments inside the loop is the only place to make a mistake — see §9 (Pitfalls).

4. Python Implementation — Iterative

from typing import Optional
 
class Node:
    def __init__(self, value, next: Optional["Node"] = None):
        self.value = value
        self.next = next
 
def reverse_iterative(head: Optional[Node]) -> Optional[Node]:
    """Reverse a singly linked list in place. O(n) time, O(1) space."""
    prev: Optional[Node] = None
    curr = head
    while curr is not None:
        nxt = curr.next       # save the rest of the list before overwriting curr.next
        curr.next = prev       # flip this node's arrow to point at the previous one
        prev = curr            # advance the "trailing" pointer
        curr = nxt             # advance the "leading" pointer
    return prev                # prev is now the original tail = new head

Line-by-line:

• nxt = curr.next saves the next node before we overwrite curr.next. Without this save, when we execute curr.next = prev, we lose the link to the rest of the list and get stuck.
• curr.next = prev is the actual reversal — pointing this node’s arrow backward.
• prev = curr; curr = nxt advances both trackers one step down the list.
• After the loop, curr is null and prev is the original tail node, which is the new head.

5. Recursive Solution

The recursive form is more elegant but uses O(n) call-stack space:

5.1 Pseudocode (Tail-First Style)

reverse_recursive(head):
    if head == null or head.next == null:
        return head                          # base: empty or singleton

    new_head := reverse_recursive(head.next)   # recursively reverse the rest
    head.next.next := head                     # head.next is the last reversed node;
                                              # make it point back at head
    head.next := null                          # head will become the new tail
    return new_head

5.2 Python

def reverse_recursive(head: Optional[Node]) -> Optional[Node]:
    """Recursive reversal. O(n) time, O(n) call-stack space."""
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    # At this point, head.next is the *last* node of the reversed-suffix —
    # i.e., it is currently the new tail. We make it point back at head.
    head.next.next = head
    head.next = None       # head becomes the new tail of the reversed list
    return new_head

5.3 Why It Works (Trace on 1 → 2 → 3)

reverse_recursive([1])
    -> reverse_recursive([2])
        -> reverse_recursive([3])
            -> [3].next == null, return [3]    # base case
        # back in reverse_recursive([2]):
        # new_head = [3]; head = [2]; head.next = [3]
        # head.next.next = head    →  [3].next = [2]
        # head.next = null         →  [2].next = null
        # return new_head = [3]
    # back in reverse_recursive([1]):
    # new_head = [3]; head = [1]; head.next = [2]
    # head.next.next = head    →  [2].next = [1]
    # head.next = null         →  [1].next = null
    # return new_head = [3]

Final: [3] → [2] → [1] → null

The trick head.next.next = head is the recursive analogue of the iterative curr.next = prev: in the recursive version, head.next plays the role of prev because after the recursive call returns, the suffix has been reversed and what was head.next is now the last node of the reversed suffix.

5.4 Tail-Recursive Variant

A more “iterative-flavored” recursion that uses an accumulator:

def reverse_tail(head: Optional[Node], prev: Optional[Node] = None) -> Optional[Node]:
    if head is None:
        return prev
    nxt = head.next
    head.next = prev
    return reverse_tail(nxt, head)        # tail call — reuses the iterative pattern

This is equivalent in shape to the iterative version, but Python does not optimize tail calls — it still uses O(n) stack. Languages that do tail-call elimination (Scheme, some Schemers in Scala) reduce this to O(1) stack. For interviews in Python/Java/JavaScript, the iterative version is the one to write when O(1) space is required.

6. Complexity

Variant	Time	Space (auxiliary)
Iterative (3-pointer)	O(n)	O(1)
Recursive (post-order)	O(n)	O(n) — call stack
Tail-recursive	O(n)	O(n) in Python (no TCO); O(1) in TCO languages

Why iterative is the canonical interview answer. A senior interviewer asking “reverse a linked list” is almost always asking for the O(1)-space iterative solution. Producing the recursive solution and stopping there suggests you don’t recognize the space concern. Show both, but lead with iterative and note that the recursive version has O(n) call-stack overhead.

Why this is so heavily drilled. Reversal exercises all the linked-list mechanics — null-checking, pointer-saving-before-mutation, loop invariants, head reassignment. If you can write iterative reversal cleanly under pressure, you can do most other linked-list problems. Interviewers know this; it’s why the question is the gateway to harder follow-ups (LC 92, LC 25, LC 234).

7. Variants

7.1 Reverse a Sublist (LC 92 — Reverse Linked List II)

Given a list and indices m, n (1-indexed), reverse only the nodes at positions m through n. Example: 1 → 2 → 3 → 4 → 5, m=2, n=4 ⇒ 1 → 4 → 3 → 2 → 5.

Approach. Walk to the (m-1)-th node (call it before), record where the reversed sublist will eventually point (before.next, which becomes the tail of the reversed sublist). Run iterative reversal on positions m through n. Reconnect.

def reverse_between(head: Optional[Node], left: int, right: int) -> Optional[Node]:
    """LC 92. Reverse the sublist between 1-indexed positions left..right."""
    if head is None or left == right:
        return head
    sentinel = Node(0, next=head)        # avoid head edge case
    before = sentinel
    for _ in range(left - 1):
        before = before.next             # before is now at position left-1
 
    # The node that will be the tail of the reversed sublist:
    sublist_tail = before.next
 
    # Reverse (right - left + 1) nodes starting at sublist_tail.
    prev: Optional[Node] = None
    curr = sublist_tail
    for _ in range(right - left + 1):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # Now `prev` is the new head of the reversed sublist; `curr` is what comes after.
 
    # Reconnect: before -> prev (new head of reversed) -> ... -> sublist_tail -> curr
    before.next = prev
    sublist_tail.next = curr
    return sentinel.next

Note the use of a sentinel to avoid special-casing left == 1. With the sentinel, before is always a real reference to the predecessor — even for the head — so the reconnection logic is uniform.

7.2 Reverse Nodes in K-Group (LC 25)

Given 1 → 2 → 3 → 4 → 5 and k = 2 ⇒ 2 → 1 → 4 → 3 → 5. With k = 3 ⇒ 3 → 2 → 1 → 4 → 5 (the trailing two are not reversed because they don’t form a complete group).

Approach. Walk through the list in groups of k. For each complete group, reverse it (using the iterative technique) and stitch into the output. Track the previous group’s tail so each new reversed group can be appended.

def reverse_k_group(head: Optional[Node], k: int) -> Optional[Node]:
    """LC 25. Reverse every k consecutive nodes; trailing < k untouched."""
    sentinel = Node(0, next=head)
    group_prev = sentinel              # tail of the most-recently-emitted reversed group
 
    while True:
        # Walk k steps from group_prev to find the k-th node (group_end).
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if kth is None:
                return sentinel.next   # not enough nodes left; done
 
        group_next = kth.next          # what follows this group
 
        # Reverse the group [group_prev.next ... kth].
        prev: Optional[Node] = group_next
        curr = group_prev.next
        while curr is not group_next:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
 
        # After reversal: group_prev.next was the original first node = new tail.
        # Stitch the reversed group in:
        new_group_head = kth                # was the k-th, now the new head of group
        new_group_tail = group_prev.next     # was the first, now the new tail
        group_prev.next = new_group_head
        group_prev = new_group_tail          # advance to next group's predecessor

This problem combines iterative reversal with careful boundary tracking. It is a frequent senior-level question because it tests fluency with the same pointer mechanics under more demanding bookkeeping.

7.3 Palindrome Linked List (LC 234)

Determine whether a singly linked list reads the same forward and backward — without using O(n) extra space.

Approach.

1. Find the middle (slow/fast pointer — see Singly Linked List §4.4).
2. Reverse the second half in place using §3.
3. Walk the first half and the reversed second half pairwise; compare values.
4. (Optional) re-reverse the second half to restore the input.

def is_palindrome(head: Optional[Node]) -> bool:
    if head is None or head.next is None:
        return True
    # 1) Find middle.
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    # 2) Reverse second half.
    second = reverse_iterative(slow)
    # 3) Compare.
    p1, p2 = head, second
    while p2 is not None:
        if p1.value != p2.value:
            return False
        p1 = p1.next
        p2 = p2.next
    return True

O(n) time, O(1) auxiliary space. The reversal is the enabling subroutine — without it you’d need a stack/array of the second half (O(n) space).

8. Pseudocode for the Recursive Variant — Two Mental Models

There are two common ways to describe the recursive reversal:

8.1 “Reverse the rest, then attach the head at the end”

reverse(head):
    if head.next == null: return head
    new_head := reverse(head.next)        # the rest is now reversed; head.next is its tail
    head.next.next := head                 # attach head after the old-last-now-tail node
    head.next := null                      # head becomes the new tail
    return new_head

This is the form in §5. Mental model: “give me a reversed sub-list, then I’ll suffix the original head onto it.”

8.2 “Build the reversal from the front using an accumulator”

reverse_acc(head, acc):
    if head == null: return acc
    next := head.next
    head.next := acc                       # prepend head onto the accumulator
    return reverse_acc(next, head)

This is the form in §5.4. Mental model: “I carry a ‘reversed-so-far’ list as I walk; each step prepends the current node.”

These two recursions illustrate the two ends of the recursion-iteration spectrum: the first is a classic “do the recursive call first, then act on the way back up” (post-order); the second is “act on the way down, recurse last” (essentially a tail call equivalent to the iterative loop). Both are correct; both are O(n) stack in Python.

9. Pitfalls

9.1 Forgetting to Save next Before Overwriting curr.next

The single most common bug:

# WRONG:
while curr is not None:
    curr.next = prev          # we just lost the rest of the list!
    prev = curr
    curr = curr.next          # this is now the wrong pointer (= prev)

After curr.next = prev, curr.next points backward, not forward. The next iteration’s curr = curr.next walks backward, infinite loop.

Fix: save next = curr.next before the flip.

9.2 Returning the Wrong Pointer

After the loop, curr is null and prev is the new head. Returning head (the original variable) returns the original head, which is now the tail of the reversed list with next = null — your caller sees a one-node list. Returning curr returns null. Return prev.

9.3 Off-By-One in LC 92 (Sublist Reversal)

Counting how many steps to advance before: for 1-indexed positions, you want before at position left - 1. For 0-indexed, you want it at position left - 1 if left ≥ 1, but the head case (left = 0) needs special handling — which is why a sentinel makes life easier.

The number of nodes to reverse is right - left + 1, not right - left. Off-by-one here is a frequent bug — one missing reversal step leaves the sublist with one node un-reversed.

9.4 Forgetting Sentinel When the Head Itself Changes

LC 206 (full list reverse) and LC 92 (sublist starting at head, left = 1) both potentially change which node is the head. Without a sentinel, you have to special-case “is left == 1?” in LC 92. With a sentinel pointing to the original head, the predecessor is always well-defined and the code branches less.

9.5 Recursive Stack Overflow

Recursive reversal uses O(n) stack frames. For lists of length 10⁶ on Python (default recursion limit 1000), it overflows. If the input might be long, use the iterative version. Some interview problems explicitly forbid stack-overflowing solutions.

9.6 Cycle Inputs

If the input list contains a cycle (e.g., from a poorly-cleaned-up earlier test), iterative reversal runs forever. The cycle is reachable, none of the next pointers ever become null, the loop never terminates. If cycle inputs are possible, run Linked List Cycle Detection first.

9.7 Mutating the Input When You Shouldn’t

Reversal mutates the original list in place. If the interview problem says “do not modify the input,” you cannot use this approach — you’d need to allocate a new list (O(n) auxiliary space). Read the problem carefully.

9.8 Accidentally Implementing Reverse-Print

for value in list: print(value) walked backward is not the same as reversing the list — one is a read-only operation that produces output in reverse, the other rewrites pointers. Sometimes the interviewer asks for reverse-print to test whether you’ll over-engineer with an in-place reversal when a stack would do the job in O(n) space without mutation. Confirm what’s being asked.

10. Diagram — The Three Pointers in Motion

flowchart LR
    subgraph "After 0 iterations"
        P0["prev = null"]
        C0["curr = [1]"]
        N0["[1] -> [2] -> [3] -> null"]
    end
    subgraph "After 1 iteration"
        P1["prev = [1]"]
        C1["curr = [2]"]
        N1["null <- [1]    [2] -> [3] -> null"]
    end
    subgraph "After 2 iterations"
        P2["prev = [2]"]
        C2["curr = [3]"]
        N2["null <- [1] <- [2]    [3] -> null"]
    end
    subgraph "After 3 iterations"
        P3["prev = [3]"]
        C3["curr = null"]
        N3["null <- [1] <- [2] <- [3]    (return prev = [3])"]
    end

What this diagram shows. Four snapshots of pointer state at the boundaries of the iterative reversal loop on input 1 → 2 → 3. The boundary between the reversed prefix (everything reachable from prev, going backward) and the unprocessed suffix (everything reachable from curr, going forward in original order) advances by one node per iteration. After n iterations, the entire list is in the reversed prefix and curr is null — termination. The new head returned is prev. The diagram reinforces the loop invariant (§2): at every point, prev is the head of the reversed-so-far, curr is the start of the still-original-order remainder, and the two halves are disjoint.

11. Common Interview Problems

Problem	LeetCode	Pattern
Reverse Linked List	LC 206	This note (iterative or recursive)
Reverse Linked List II (sublist)	LC 92	§7.1 — sentinel + iterative reversal in middle
Reverse Nodes in K-Group	LC 25	§7.2 — iterative reversal per group, stitch
Palindrome Linked List	LC 234	§7.3 — find middle + reverse half + compare
Reorder List	LC 143	Find middle + reverse second half + interleave
Add Two Numbers II	LC 445	Reverse both lists + pairwise add (or use stacks)
Swap Nodes in Pairs	LC 24	Special case of LC 25 with k=2
Reverse Doubly Linked List	—	Swap prev/next on every node, swap head/tail roles

The first three are the staples. LC 206 is asked in roughly 1 of every 3 phone screens; LC 92 and LC 25 are common onsites. Together they form a graduated test: can you do iterative reversal cleanly (LC 206), can you handle bookkeeping for partial reversal (LC 92), can you handle batch reversal with stitching (LC 25)?

12. Open Questions

• Is there a published algorithm for reversing a linked list that beats O(n) time? Almost certainly not — every node must have its next pointer rewritten, which is Ω(n) work. But “rewriting from a higher-level structure” (e.g., a linked list of blocks) is a meaningful real-world variant.
• When does the recursive version’s clarity outweigh its O(n) stack cost in production code? Probably never for unbounded input. The iterative version is just as readable once you know the three-pointer pattern.

13. See Also

• Singly Linked List — the structure we’re reversing
• Doubly Linked List — reversing a DLL: swap prev/next on every node, swap head/tail
• Linked List Cycle Detection — companion technique; combines naturally for cycle-aware processing
• Merge Two Sorted Lists — another core pointer-rewire operation
• Two Pointers — the family this technique belongs to
• Big-O Notation
• SWE Interview Preparation MOC