206. Reverse Linked List

Reversing a singly linked list is the exercise that forces you to actually watch the pointers, and once the three-variable dance is muscle memory, half of the linked-list pattern stops being scary. It shows up as a subroutine inside harder problems, so it earns its place on every warm-up list.

The problem

You’re handed the head of a singly linked list and asked to flip it: the node that was last becomes the new head, every next pointer turns around, and you return the new head. (Full statement on LeetCode.)

So 1 -> 2 -> 3 -> null comes back as 3 -> 2 -> 1 -> null. Nothing gets copied — you’re rewiring the list you already have.

Intuition: walk once, flipping each arrow as you pass

A singly linked list only lets you move forward, which is exactly the trap. The moment you set curr.next = prev to flip an arrow, you’ve destroyed the link you needed to reach the rest of the list. So the whole trick is to grab the next node before you overwrite the pointer.

That’s why three variables, not two:

• prev — the part already reversed, sitting behind you.
• curr — the node whose arrow you’re flipping right now.
• next — a one-step-ahead bookmark so you don’t lose the tail.

Each iteration does four moves in a fixed order: save next, flip curr.next to point back at prev, then slide both prev and curr forward by one. When curr falls off the end as null, prev is standing on the old tail — the new head. One pass, $O(n)$ time, and no extra list.

Solution

The iterative flip is the one to reach for — it reverses in place with constant extra space:

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;      // reversed portion starts empty
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;  // bookmark before we clobber it
            curr.next = prev;           // flip this arrow backward
            prev = curr;                // grow the reversed portion
            curr = next;                // advance into the untouched tail
        }
        return prev;                    // old tail is the new head
    }
}

The recursive version reads more cleanly but pays for it in stack space. It recurses to the end, then rewires on the way back up:

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;  // empty or single node
        ListNode newHead = reverseList(head.next);           // reverse everything after head
        head.next.next = head;   // the node ahead now points back at head
        head.next = null;        // head becomes the new tail
        return newHead;          // same head bubbles all the way up
    }
}

The line head.next.next = head is the one that trips people up: head.next is still the original next node, and we make it point back at head. Then we sever head’s forward link so the old front becomes the new end.

Complexity

Approach	Time	Space
Iterative	$O(n)$	$O(1)$
Recursive	$O(n)$	$O(n)$

Both touch every node once. The recursive one carries an $O(n)$ call stack, so on a very long list it can overflow where the iterative version wouldn’t.

In an interview

Narrate the pointer order out loud before writing: “save next, flip current, move both forward.” The classic bug is flipping curr.next before saving next — do that and you’ve cut the list in half and orphaned the rest. Saying the order first shows you understand why the bookmark exists, which is the whole point of the question.

Have the edge cases ready too: an empty list (head == null) and a single node should both just fall out of the loop and return correctly — worth stating so the interviewer doesn’t have to ask. If they push for the recursive form, mention the $O(n)$ stack as the trade-off.

This same pointer discipline powers Reorder List, which reverses the back half in place, and it pairs naturally with the fast/slow traversal in Linked List Cycle. The linked-list pattern hub collects the rest.

References

• LeetCode 206 — Reverse Linked List