162. Reverse Linked List

Walk the list once, and at each node flip its next pointer to point backwards to the node we just processed. The trick is keeping three pointers — the one we're rewiring, the one before, and the one after — so the rest of the list isn't lost mid-flip.

The mental picture

We have a list 1 → 2 → 3 → None and want to produce 3 → 2 → 1 → None.

Imagine standing at each node in turn and flipping its arrow. The danger is that once you flip 2's arrow to point at 1, you've lost the way to 3. So before flipping, we save a pointer to whatever was next.

The three pointers

• prev — the previously visited node (will become curr's new next). Starts as None.
• curr — the node we're currently flipping. Starts as head.
• nxt — saved reference to curr.next so we can move on after rewiring.

Steps

1. Initialise prev = None, curr = head.
2. While curr is not None:
   • nxt = curr.next ← remember what's coming
   • curr.next = prev ← flip the arrow
   • prev = curr ← step prev forward
   • curr = nxt ← step curr forward
3. Return prev (it's the new head).

Walk-through

head = 1 → 2 → 3 → None.

Result: 3 → 2 → 1 → None. ✓

Why we need nxt

After we set curr.next = prev, curr.next no longer points at the next node — it points back to prev. If we then write curr = curr.next, we'd walk backwards. Saving nxt ahead of time keeps the forward path alive.

Edge cases

• Empty list (head is None): the while body never runs; return prev = None.
• Single node: one iteration sets curr.next = None (it was already None), then prev = node, curr = None; return node.

Complexity

• Time: O(n) — each node is visited exactly once.
• Space: O(1) — three pointer variables.

import java.util.*;

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

    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }
}

Trust recursion: "reverse the tail" gives back the new head of an already-reversed sub-list. All we have to do at this level is hook the current node onto the end of that reversed tail.

The recursive insight

Suppose the recursion correctly reverses the sub-list starting at head.next. Then we get back a new head, and the original head.next is now the last node of the reversed tail (because reversal flips the order).

So all that's left at this call: append head after the reversed tail's last node, and null out head.next so the new last node terminates cleanly.

Steps

1. Base case: if head is None or head.next is None, the list of length 0 or 1 is already reversed — return head.
2. Recurse: new_head = reverseList(head.next).
3. Hook current node onto the tail: head.next.next = head. Reading literally: "the node that used to be next to head is now the last node of the reversed sub-list, and we point its next back at head".
4. Cap the list: head.next = None.
5. Return new_head.

Walk-through

head = 1 → 2 → 3 → None.

Recursive descent:

reverseList(1)  → calls reverseList(2)
  reverseList(2) → calls reverseList(3)
    reverseList(3) → base case, returns 3
  back in reverseList(2): head=2, head.next=3
    head.next.next = head  →  3.next = 2  →  list: 3 → 2 → 2 (looped briefly)
    head.next = None       →  list: 3 → 2 → None
    return 3
back in reverseList(1): head=1, head.next=2
  head.next.next = head  →  2.next = 1  →  list: 3 → 2 → 1 → 1 (loop)
  head.next = None       →  list: 3 → 2 → 1 → None
  return 3

Result: 3 → 2 → 1 → None. ✓

Why head.next.next = head works

After the recursive call returns, the structure looks like:

new_head → ... → head.next       (reversed sub-list, ending at the original head.next)
head → head.next                 (original arrow still in place)

Setting head.next.next = head extends the reversed sub-list by one node. Then head.next = None makes head the new last node.

Edge cases

• Empty list / single node: the base case returns immediately.
• Deep recursion: Python's default recursion limit (1000) means very long lists may trip it. The iterative version doesn't have that risk.

Complexity

• Time: O(n) — each node is visited once in the recursion.
• Space: O(n) — the recursion stack reaches depth n.