Stage 1: Foundations·Linked Lists

Easy#2066 min readLinked ListsPointer ManipulationLeetCode

Reverse Linked List

Three pointers

Three pointers: prev, curr, next. Draw it out. Do both iterative and recursive.

Published Apr 15, 2026

Problem

Given the head of a singly linked list, reverse the list and return the new head.

Input

head = [1,2,3,4,5]

Output

[5,4,3,2,1]

Input

head = [1,2]

Output

[2,1]

Intuition

Reversing a linked list is not about values. It is about rewiring pointers.

At any moment, the list splits into two regions:

a prefix that has already been reversed
a suffix that has not been processed yet

That gives the entire invariant. Keep a pointer to the reversed prefix, a pointer to the current node, and a temporary pointer to preserve the rest of the list before you overwrite next.

Once you see the invariant, the algorithm is mechanical. Every node moves from the unreversed side to the reversed side exactly once.

Approach

Iterative Three Pointers

TimeO(n)

SpaceO(1)

Recommended

Walk the list once. For each node:

Save curr.next.
Point curr.next at prev.
Advance prev and curr.

When curr falls off the end, prev is the new head.

impl Solution {
    pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut prev: Option<Box<ListNode>> = None;

        while let Some(mut curr) = head {
            head = curr.next.take();
            curr.next = prev;
            prev = Some(curr);
        }

        prev
    }
}

Rust · runnable

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;

  while (curr !== null) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  return prev;
}

TypeScript · runnable

Recursive

TimeO(n)

SpaceO(n)

The recursive version expresses the same invariant from the other direction: reverse the suffix first, then stitch the current node onto the tail of that reversed suffix.

This is elegant, but the stack cost is real. Use it to understand the shape; use the iterative version in production.

impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        fn rev(
            node: Option<Box<ListNode>>,
            prev: Option<Box<ListNode>>,
        ) -> Option<Box<ListNode>> {
            match node {
                Some(mut curr) => {
                    let next = curr.next.take();
                    curr.next = prev;
                    rev(next, Some(curr))
                }
                None => prev,
            }
        }

        rev(head, None)
    }
}

Rust · runnable

function reverseList(head: ListNode | null): ListNode | null {
  const rev = (node: ListNode | null, prev: ListNode | null): ListNode | null => {
    if (node === null) return prev;
    const next = node.next;
    node.next = prev;
    return rev(next, node);
  };

  return rev(head, null);
}

TypeScript · runnable

Trace

Iterative reversal on head = [1,2,3]:

step	curr	next saved	prev after
start	1	2	[]
1	1	2	[1]
2	2	3	[2,1]
3	3	null	[3,2,1]

prev ends at the new head. The original head pointer has been walked to null.

Edge cases

Empty list — return null immediately.
Single node — no pointer rewrite is needed; the list is unchanged.
Very long list — the recursive version uses O(n) call stack; the iterative version does not.

Takeaway

Linked-list reversal is the canonical pointer-rewrite problem. Once you can hold the three-pointer invariant in your head, the rest of the linked-list track becomes much easier: merge, reorder, and even k-way merge all reduce to the same discipline of preserving next before overwriting it.

Easy#21

Merge Two Sorted Lists

Merge step of merge sort. In Rust, practice with Option<Box<ListNode>>.

Easy#141

Linked List Cycle

Floyd’s tortoise and hare. Understand WHY fast catches slow.

Medium#143

Reorder List