4.9.1 — Reverse Linked List

LeetCode 206 · Easy · ★ Blind 75

The problem

Reverse a singly linked list and return the new head.

1 → 2 → 3 → 4 → 5 → null
becomes
5 → 4 → 3 → 2 → 1 → null

The pattern

Reversing means every next pointer turns around. Walk the list once, and at each node point it back at the node you just came from.

The only real difficulty is that overwriting curr.next destroys your way forward. So save the next node before you overwrite the pointer. That is the entire problem.

Three pointers: prev (where you came from), curr (where you are), and a temporary holding curr.next.

The solution

Python

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head

        while curr:
            nxt = curr.next      # save the way forward
            curr.next = prev     # turn the pointer around
            prev = curr          # everybody shuffles along
            curr = nxt

        return prev              # curr is None, prev is the last real node

TypeScript

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

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

  return prev;
}

prev starts as null, which is exactly right: the old head becomes the new tail, and a tail points at nothing.

The loop ends when curr is null, so the new head is prev, not curr. Returning curr gives null every time, and that is the classic bug.

Trace

step	prev	curr	list so far
start	null	1	1→2→3
after 1	1	2	1→null, 2→3
after 2	2	3	2→1→null
after 3	3	null	3→2→1→null

Return prev = 3. ✓

The recursive version

def reverseList(self, head):
    if not head or not head.next:
        return head
    new_head = self.reverseList(head.next)   # reverse everything after me
    head.next.next = head                    # the node after me points back at me
    head.next = None                         # and I point at nothing
    return new_head

head.next.next = head is the line to slow down on. If head is node 1 and node 2 follows it, then after the recursive call the rest of the list is already reversed and node 2 is its tail. head.next is node 2, so head.next.next = head makes node 2 point back at node 1 — attaching node 1 to the end.

Then head.next = None, because node 1 is now the tail.

It is elegant and it is O(n) space, because the call stack holds one frame per node. On a 100,000-node list that overflows. The iterative version is the one to write.

Complexity

O(n) time, O(1) space for the iterative version.

Why this problem matters

It is the single most reused subroutine in the linked-list group. Reordering a list, checking whether it is a palindrome, adding numbers stored backwards, reversing in groups of k — all of them reverse something. Get this into muscle memory and half of 4.9 becomes assembly work.

Where this goes next

• Reverse Linked List II — reverse only the portion between positions left and right. Same loop, plus pointers to the nodes just outside the reversed section so you can stitch it back in.
• Reverse Nodes in K-Group — reverse every block of k. That is 4.9.11.
• Palindrome Linked List — find the middle, reverse the second half, compare.

Next: 4.9.2 Merge Two Sorted Lists — the problem that introduces the dummy head, which removes almost every edge case in this chapter.