Reverse Linked List (LC 206)

Pattern: Linked List — reversal (iterative + recursive)
Difficulty: Easy
Key Concept: Change each node’s next to point to the previous node while walking forward; track prev and curr.

Problem Statement

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

Input: head of list (may be null).
Output: new head after reversal.

Example: 1 -> 2 -> 3 -> 4 -> 5 becomes 5 -> 4 -> 3 -> 2 -> 1.

---

1. Algorithm & Pseudocode

Brute force

1. Copy all values into an ArrayList, reverse the list, rebuild a new linked list from reversed values.
2. Uses O(n) extra structure and new nodes (or overwrites values only—still extra array).

Pseudocode:

vals = []
walk head, push each val to vals
reverse vals array
build new list from vals

Optimal

Iterative:

1. prev = null, curr = head.
2. While curr != null: next = curr.next, curr.next = prev, prev = curr, curr = next.
3. Return prev.

Recursive:

1. Base: if head is null or head.next is null, return head.
2. newHead = reverseList(head.next); then head.next.next = head, head.next = null.
3. Return newHead.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why pointer surgery beats copying: Interview expectation is in-place reversal in O(1) extra space (iterative).

Why save next before rewiring: Once you set curr.next = prev, you lose the forward link unless you stored it.

Recursion uses O(n) stack but expresses “reverse rest, then attach head at tail.”

---

3. The Dry Run

Iterative on 1 -> 2 -> 3 (simplified).

step	prev	curr	next	action
init	null	1	—	—
1	null	1	2	1.next = null
2	1	2	3	2.next = 1
3	2	3	null	3.next = 2
end	3	null	—	return 3

Final chain (ASCII):

null <--- 1 <--- 2 <--- 3   (head at 3)

---

4. Java Solution

Brute Force

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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

public class Solution {
    public ListNode reverseList(ListNode head) {
        List<Integer> vals = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) {
            vals.add(p.val);
        }
        Collections.reverse(vals);
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : vals) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

Time: O(n). Space: O(n) for values + new nodes.

Optimal (iterative)

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

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

Time: O(n). Space: O(1).

Optimal (recursive)

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

Time: O(n). Space: O(n) call stack.

---

5. The “Java vs. Others” Edge

• ListNode is a class reference: reassignment does not copy the node—only pointers move.
• Iterative reversal is preferred when stack depth is a concern (very long lists).
• Dummy node not required for reversal; optional for other list problems.

---

6. Complexity Summary

Approach	Time	Space	Notes
Copy + rebuild	O(n)	O(n)	New list objects
Iterative reverse	O(n)	O(1)	In-place
Recursive reverse	O(n)	O(n)	Clean code, stack cost

---

ASCII — before and after

Before (head → 1):

head
  |
  v
+---+    +---+    +---+
| 1 |--> | 2 |--> | 3 |--> null
+---+    +---+    +---+

After (newHead → 3):

newHead
   |
   v
+---+    +---+    +---+
| 3 |--> | 2 |--> | 1 |--> null
+---+    +---+    +---+

One iterative step (rewire curr):

prev       curr     next
 |           |        |
 v           v        v
+---+       +---+    +---+
| p |<------| c |--> | n |--> ...
+---+       +---+    +---+