Reverse Linked List

Reverse a singly linked list and return the new head. (LC 206)

The recipe

Say before you type: "Walk the list flipping one arrow per step. Three pointers — prev, curr, and a saved next — and the order of operations is the entire problem."

The four lines, in the only order that works:

1. Save curr.next — flip first and you've lost the rest of the list forever.
2. Flip: curr.next = prev.
3. Advance prev to curr.
4. Advance curr to the saved next.

The code

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;
  while (curr) {
    const next = curr.next; // 1. SAVE (or you lose the rest of the list)
    curr.next = prev;       // 2. FLIP
    prev = curr;            // 3. advance prev
    curr = next;            // 4. advance curr
  }
  return prev; // curr is null; prev is the new head
}

Why this shape

A singly linked list only points forward, so reversing it means rewriting every next — and the moment you rewrite one, you've cut your own path forward. The saved next is the lifeline. prev starts at null deliberately: the first node's flipped arrow should point at nothing, because it's about to become the tail.

The loop invariant worth narrating: at the top of each iteration, everything before curr is already reversed and prev is its head; everything from curr on is untouched. When curr runs off the end, "already reversed" is the whole list.

Complexity

	Cost	Because
Time	O(n)	One visit per node, constant work each
Space	O(1)	Relinking in place — three pointers, no new nodes

Traps

• Returning curr (always null at the end) instead of prev.
• Flipping before saving. Trace 1 → 2 → 3 on paper once per rep — it takes thirty seconds and catches the order slip immediately.

The recursive version — know the trade-off

function reverseListRec(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  const newHead = reverseListRec(head.next);
  head.next.next = head; // point the next node back at me
  head.next = null;      // sever my forward pointer
  return newHead;
}

Elegant, and O(n) stack space where the loop is O(1) — say that unprompted. A 100k-node list stack-overflows the recursive version; iterative is the production answer.

The pattern this trains

Pointer surgery under an invariant. Merge Two Sorted Lists (LC 21), palindrome list, reverse-in-k-groups — all the same discipline: know what's been rewired, keep a lifeline to what hasn't.