#206 Reverse Linked List

Easysolve on LeetCode ↗

frequently reported atAdobe Apple Microsoft Bloomberg Oracle Google

the problem

In plain words

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

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

out [5,4,3,2,1]

in head = [1,2]

out [2,1]

in head = []

out []

0 ≤ number of nodes ≤ 5000
-5000 ≤ Node.val ≤ 5000

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternIn-place linked-list rewiring

You don't move nodes — you flip arrows. Walk once; at each node point next back at the previous node. Save the forward link first.

solutions

From brute force to optimal

A stack hands nodes back in reverse order; relink them as they pop.

Push every node.
Pop each one and append it to a new chain.
Set the last node's next to null.

timeO(n)

Each node is pushed and popped once.

spaceO(n)

The stack holds all n nodes.

javajava.util.*

1class Solution {2    public ListNode reverseList(ListNode head) {3        Deque<ListNode> stack = new ArrayDeque<>();4        for (ListNode p = head; p != null; p = p.next) stack.push(p);5        ListNode dummy = new ListNode();6        ListNode tail = dummy;7        while (!stack.isEmpty()) {       // pops come out last-first8            tail.next = stack.pop();9            tail = tail.next;10        }11        tail.next = null;                // old head still pointed forward: cut it12        return dummy.next;13    }14}

Reverse everything after head, then hook head onto the end of that reversed part.

Base case: 0 or 1 node.
newHead = reverse(head.next).
head.next.next = head; head.next = null.
Return newHead.

timeO(n)

One call per node.

spaceO(n)

n stack frames — risky for very long lists.

javajava.util.*

1class Solution {2    public ListNode reverseList(ListNode head) {3        if (head == null || head.next == null) return head; // last node = new head4        ListNode newHead = reverseList(head.next);  // reverse everything after me5        head.next.next = head;                      // my old next now points back at me6        head.next = null;                           // I'm the tail of the reversed part (for now)7        return newHead;                             // pass the new head all the way up8    }9}

sim

Recursion dry run

loading simulation…

javajava.util.*

1class Solution {2    public ListNode reverseList(ListNode head) {3        if (head == null || head.next == null) return head; // last node = new head4        ListNode newHead = reverseList(head.next);  // reverse everything after me5        head.next.next = head;                      // my old next now points back at me6        head.next = null;                           // I'm the tail of the reversed part (for now)7        return newHead;                             // pass the new head all the way up8    }9}

Keep prev (reversed part) and curr (rest). Save next, flip curr.next, advance both.

prev = null, curr = head.
next = curr.next.
curr.next = prev.
prev = curr; curr = next.
Return prev.

timeO(n)

One pass, constant work per node.

spaceO(1)

Three references.

javajava.util.*

1class Solution {2    public ListNode reverseList(ListNode head) {3        ListNode prev = null, curr = head;4        while (curr != null) {5            ListNode next = curr.next;6            curr.next = prev;7            prev = curr;8            curr = next;9        }10        return prev;11    }12}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public ListNode reverseList(ListNode head) {3        ListNode prev = null, curr = head;4        while (curr != null) {5            ListNode next = curr.next;6            curr.next = prev;7            prev = curr;8            curr = next;9        }10        return prev;11    }12}

in the room

How to say it in the interview

talk track

State the invariant: "prev is the head of the reversed part, curr is the first node not yet reversed."
Write the four lines in order: save, flip, advance prev, advance curr. Explain why save comes first.
Dry-run on [1,2,3] and mention empty and single-node lists work without special cases.
Offer the recursive version as a follow-up and note its O(n) stack space.
For the recursive one, say the key sentence: "after the call returns, head.next is the tail of the reversed rest."

traps

Returning curr (it's null at the end) instead of prev.
Forgetting head.next = null in the recursive version — creates a 2-node cycle.
Returning head instead of newHead from the recursive case.

what they ask next

Follow-ups

Reverse only positions left..right?

That's Reverse Linked List II (LC 92, below): stand on the node before left (use a dummy) and reverse right − left + 1 nodes, reconnecting both ends. One pass, O(1) space.

Reverse k nodes at a time?

That's Reverse Nodes in k-Group (LC 25, below): check that k nodes remain, reverse exactly those k, connect the previous block's tail to the new block head, repeat.

Palindrome check in O(1) space?

Palindrome Linked List (LC 234, below): find the middle with slow/fast, reverse the second half, compare the halves node by node (and reverse back).

before you submit

Edge cases to test

Empty list → return null.
One node → return it unchanged.
Two nodes — the smallest case where an off-by-one shows up.

practise next