Reverse Linked List

1. Problem & Core Objective

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

input:   1 → 2 → 3 → 4 → 5 → null
output:  5 → 4 → 3 → 2 → 1 → null

Constraints: 0 <= n <= 5000 · -5000 <= Node.val <= 5000

What's actually being tested: whether you can manipulate pointers without losing the list. Every later question in this section reuses this routine — Reorder List calls it, Reverse Nodes in K-Group calls it repeatedly, Palindrome checks call it. Get this one automatic.

The real question is a small one: can you rewire a structure while you're standing on it?

2. First-Principles Thought Process

What reversal actually means

A linked list is defined entirely by its next pointers. Reversing it doesn't move any node — it flips every arrow.

before:  1 → 2 → 3 → null
after:   null ← 1 ← 2 ← 3

Node 1 is the same object in both pictures. Only 1.next changed, from 2 to null.

The problem with flipping in place

Try the naive thing on node 1:

cur.next = prev;      // 1.next was 2 — now it's null

You just destroyed the only reference to node 2. The rest of the list is unreachable, and it's gone.

So the rule is: save the next node before you overwrite the pointer to it.

The three pointers

That gives exactly three things to track:

• prev — the node the current one should now point at (starts null, since the old head becomes the new tail)
• cur — the node being rewired
• next — a temporary holding the rest of the list

Each iteration flips one arrow and shuffles all three forward one position.

Why prev starts at null

The old head becomes the new tail, and a tail points at null. Initializing prev = null makes that fall out of the same line that handles every other node — no special case for the first one.

3. Solution Paths

Approach 1 — Collect into a list, rebuild (brute force)

public ListNode reverseList(ListNode head) {
    List<ListNode> all = new ArrayList<>();
    for (ListNode p = head; p != null; p = p.next) all.add(p);
    if (all.isEmpty()) return null;

    for (int i = all.size() - 1; i > 0; i--) all.get(i).next = all.get(i - 1);
    all.get(0).next = null;                       // old head is the new tail
    return all.get(all.size() - 1);
}

Walk the list into an array, then rewire from the back.

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "Why do you need the array at all?"

I don't — I'm using it to solve the "I destroyed my next pointer" problem by keeping every node reachable. But I only ever need one node of lookahead, not all of them. A single temporary variable does the same job, which drops the space to O(1).

"Is O(n) extra space actually a problem at n <= 5000?"

Not for correctness — it runs fine. But O(1) is achievable with strictly less code, and the interviewer is asking this question specifically to see the pointer manipulation. Reaching for an array reads as avoiding the thing being tested.

"Could you copy the values instead of rewiring nodes?"

You could collect the values, then walk the list again writing them back in reverse. It's O(n) time and space and it works here. But it's a different operation — it mutates payloads rather than structure — and it breaks the moment nodes carry identity that matters, like the random pointers in question 5. Rewiring is the honest answer.

Approach 2 — Three-pointer iteration (optimal)

public ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;    // 1. save the rest of the list
        cur.next = prev;             // 2. flip this one arrow
        prev = cur;                  // 3. prev advances
        cur = next;                  // 4. cur advances
    }
    return prev;                     // cur is null; prev is the new head
}

Trace — 1 → 2 → 3:

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Why return prev and not cur?"

The loop exits when cur is null — it has walked off the end. prev is one behind, sitting on the last node it processed, which is the original tail and therefore the new head. Returning cur would return null every time.

⭐ "What happens if you reorder those four lines?"

Three of the four orderings break. If cur.next = prev runs before saving next, the rest of the list is unreachable. If prev = cur runs before cur.next = prev, you set cur.next = cur — a self-loop, and an infinite list. The sequence save → flip → advance → advance is forced, not stylistic.

"Does this handle an empty list?"

Yes, and without a special case. cur = head = null, the loop body never runs, and it returns prev, which is still null — the correct reversal of an empty list. A single node works too: one iteration sets 1.next = null and returns 1.

"Is the original list still usable afterwards?"

No — it's destroyed. The caller's head now points at the new tail, so walking from it yields one node. That's fine when the caller reassigns (head = reverseList(head)), but it's worth stating out loud: this mutates in place rather than returning a new list.

Approach 3 — Recursion

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;   // base: empty or single

    ListNode newHead = reverseList(head.next);   // reverse everything after head
    head.next.next = head;                       // make the next node point back
    head.next = null;                            // and sever the forward link
    return newHead;                              // the deepest node, unchanged
}

The trick is head.next.next = head. At this point head.next is the node after head — which, after the recursive call, is now the tail of the reversed remainder. Pointing it back at head appends head to that tail.

• Time O(n) · Space O(n) for the call stack

Counter-questions on this approach

⭐ "You said O(1) space matters. This is O(n). Which do you submit?"

The iterative one. The recursion's stack is real memory — at n = 5000 that's 5000 frames, and on a longer list it's a StackOverflowError. The recursive version is elegant and worth showing, but the iterative one is strictly better on space with no readability cost.

"Why can't the JVM optimize the stack away?"

The recursive call isn't in tail position — work happens after it returns (head.next.next = head). Even rewritten tail-recursively, the JVM doesn't perform tail-call elimination, unlike Scala or most functional runtimes. So the frames are unavoidable in Java.

"Walk me through head.next.next = head on 1 → 2."

reverseList(2) hits the base case and returns node 2, so newHead = 2. Now head is 1 and head.next is 2, so head.next.next = head sets 2.next = 1. Then head.next = null makes 1.next = null, giving 2 → 1 → null. Without that second line, 1.next would still be 2 and you'd have a two-node cycle.

"What does the base case head.next == null do that head == null doesn't?"

It stops one node early and returns the final node, which becomes the new head and gets passed back up untouched through every frame. head == null alone would recurse one level further and return null, losing the new head.

Comparison

4. Why the Optimal Wins

All three are O(n) time — you must touch every node to flip every arrow, so there's no beating that. The separation is entirely space.

The array version stores n nodes to solve a problem that needs one node of lookahead. The recursion stores n stack frames for the same reason. The iterative version recognises that the lookahead is one deep and uses one variable.

The framing worth keeping:

To rewire a structure you're standing on, save your escape route before you overwrite it.

That single idea — hold next before clobbering cur.next — recurs in every pointer-manipulation problem in this section.

5. Java Prerequisites

The node

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

The reversal, as a reusable block — memorize this:

ListNode prev = null, cur = head;
while (cur != null) {
    ListNode next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}
return prev;

Walking without destroying — the read-only idiom, for comparison:

for (ListNode p = head; p != null; p = p.next) { ... }

Null-safety. cur.next throws NullPointerException when cur is null. Every loop condition in this section exists to prevent that — while (cur != null) here, while (fast != null && fast.next != null) for two-pointer walks.

6. Interview Communication Guide

Clarifying questions: Singly or doubly linked (singly)? Reverse in place or return a new list (in place is expected)? Can the list be empty (yes)? Iterative or recursive preferred (offer both)?

The pitch

"Reversing doesn't move any nodes — it flips every next pointer. Node 1 stays where it is; 1.next just changes from 2 to null.

The catch is that overwriting cur.next destroys the only reference to the rest of the list. So I save the next node before flipping.

That gives three pointers: prev — what the current node should now point at, starting at null because the old head becomes the new tail; cur — the node being rewired; and a temporary next.

Each iteration is four lines: save next, flip cur.next to prev, then advance both. When cur walks off the end, prev is sitting on the old tail — the new head.

O(n) time, O(1) space. Empty and single-node lists fall out with no special case.

There's a recursive version that's arguably prettier, but it's O(n) stack and overflows on a long list, so I'd submit the iterative one."

Edge cases to volunteer:

The 5000-node case is the one to name — it's the concrete reason to prefer the iterative version, not a stylistic preference.

7. Follow-Up Questions — Modified Constraints

⭐ "Reverse only nodes between positions m and n."

LeetCode 92. Walk to position m-1 and hold it, run the same three-pointer loop for n - m + 1 steps, then reattach both ends. The reversal is identical; the work is in the stitching — which is why a dummy head helps, since m = 1 otherwise needs its own branch.

⭐ "Reverse in groups of k, leaving a trailing partial group alone."

That's question 11 in this section. Check that k nodes remain, reverse exactly k, recurse or iterate on the rest, and stitch. The inner loop is this function with a counter.

"What if the list were doubly linked?"

Swap next and prev on every node and return the old tail. It's a single pass, but each node needs both pointers exchanged rather than one overwritten — and no temporary is needed, because prev already holds the escape route.

"Reverse it without modifying the input — return a new list."

Walk forward allocating a new node per element and pushing each to the front of the result. O(n) time and O(n) space, which is unavoidable since you're building n new nodes. Useful when the caller still needs the original.

"Check whether the list is a palindrome."

LeetCode 234. Find the middle with slow/fast, reverse the second half with exactly this routine, then walk both halves in step. O(n) time, O(1) space — and politely restore the list afterwards, since you mutated the caller's data.

"What if two threads reversed the same list concurrently?"

It corrupts — interleaved pointer writes can produce cycles or lost nodes, and there's no atomicity across the four lines. You'd need a lock around the whole traversal, or an immutable/copy-on-write approach. Worth raising because in-place mutation of shared structure is exactly where this pattern gets dangerous in production.