LeetCode 206 – Reverse Linked List

Reverse Linked List is the most-asked linked list question there is, and it is asked because the iterative solution is four assignments whose order is the entire problem. Everyone knows what it does; the test is whether you can write it without losing the rest of the list.

The problem

Reverse a singly linked list and return the new head.

1 -> 2 -> 3 -> 4 -> 5   ->   5 -> 4 -> 3 -> 2 -> 1
1 -> 2                  ->   2 -> 1
[]                      ->   []
[1]                     ->   [1]

Three pointers, in one order

Reversing means pointing each node at its predecessor. The moment you do that, the pointer to the successor is gone — so it has to be saved first.

previous = null
current  = head

while current != null:
    next = current.next        1. SAVE, before it is destroyed
    current.next = previous    2. reverse this link
    previous = current         3. advance previous
    current = next             4. advance current

return previous                current is null; previous is the last node

Step 1 is the one people drop, and dropping it truncates the list to a single node — you keep the head, point it at null, and lose everything else. It is the same rule as Binary Tree Upside Down and Flatten Binary Tree: save what the write is about to destroy.

Returning previous and not current is the second thing to get right. The loop exits when current is null, one step past the end, so the new head is the node behind it.

null <- 1 <- 2 <- 3    4 -> 5
                 ^     ^
            previous  current

Java

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        ListNode current = head;

        while (current != null) {
            ListNode next = current.next;   // save it BEFORE the link is overwritten

            current.next = previous;        // reverse
            previous = current;             // advance both
            current = next;
        }

        return previous;   // current is null; previous is the new head
    }
}

previous starts at null, which is exactly right: the original head becomes the tail, and a tail's next is null. No special case for it.

An empty list skips the loop entirely and returns null. A single node points at null and returns itself. Both fall out — worth checking rather than adding guards for.

Python

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        previous, current = None, head

        while current:
            current.next, previous, current = previous, current, current.next

        return previous

The single tuple assignment does all four steps at once, and it is correct for a specific reason: the entire right-hand side — including current.next, which is read before anything is rebound — is evaluated first. That removes the need to save the successor manually.

It is also harder to read, and the explicit four-line version is a perfectly good answer. If you write the compressed one, be ready to explain the evaluation order; if you cannot, write the long one.

The recursive version

    ListNode reverseListRecursive(ListNode head) {
        if (head == null || head.next == null) return head;

        // Everything after head is already reversed; newHead is the deepest node.
        ListNode newHead = reverseListRecursive(head.next);

        head.next.next = head;   // the node after head now points BACK at head
        head.next = null;        // head becomes the tail

        return newHead;          // threaded back unchanged
    }

head.next.next = head is the line worth staring at. At this point head.next is the node that was originally after head and is now the last node of the reversed remainder — so pointing its next back at head appends head to the end. Then head.next = null makes it the tail.

newHead is passed straight up untouched, the same way it is in Binary Tree Upside Down — the recursion is providing traversal order, not computing anything on the way back.

O(n) stack, so it overflows on a long list. Offer it as the elegant version and the iterative one as the answer.

Complexity

One pass, three pointers, no allocation. The list is reversed in place, so the caller's original head now points at null — worth mentioning, because it means the original ordering is not recoverable without reversing again.

Why this problem is everywhere

It is a component of half the harder list problems, and being able to produce it without thinking is what makes those tractable:

The last three all follow the same recipe — find the middle with fast/slow pointers, reverse one half, walk the two halves together — which combines this with problem 141's two-pointer trick. Those two together cover most of the list section.

What the interviewer is checking

• Saving the successor before overwriting the link.
• Returning previous, not current.
• That previous starts at null, making the old head a proper tail.
• Empty list and single node, with no guards.
• That you can write it without hesitating — it is a building block, not a puzzle.
• The recursive version, and that it is O(n) stack.