Pattern 07: In-place Reversal of a Linked List

0. The Template (Copy-Paste Skeleton)

Two skeletons — reverse and dummy head — plus one rule: when a problem might delete or replace the head, allocate a dummy node and you delete an entire class of edge cases.

// TEMPLATE A — REVERSE A LIST (iterative, O(1) space) — memorise the 4-line dance
ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;   // 1. SAVE   the rest of the list
        curr.next = prev;            // 2. FLIP   the pointer backwards
        prev = curr;                 // 3. ADVANCE prev
        curr = next;                 // 4. ADVANCE curr
    }
    return prev;                     // prev is the NEW head (curr is null here)
}

// TEMPLATE B — DUMMY HEAD (any problem that may modify/remove the first node)
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;

while (prev.next != null) {
    if (shouldRemove(prev.next)) prev.next = prev.next.next;   // unlink
    else                          prev = prev.next;            // advance
}
return dummy.next;               // never `return head` — head itself may be gone

// TEMPLATE C — REVERSE A SUB-LIST [left, right] (LC 92)
ListNode dummy = new ListNode(0, head);
ListNode beforeLeft = dummy;
for (int i = 1; i < left; i++) beforeLeft = beforeLeft.next;

ListNode prev = null, curr = beforeLeft.next;
for (int i = 0; i <= right - left; i++) {          // reverse exactly (right-left+1) nodes
    ListNode next = curr.next;
    curr.next = prev; prev = curr; curr = next;
}
beforeLeft.next.next = curr;      // old sub-head now points at the tail remainder
beforeLeft.next = prev;           // stitch the reversed block back in
return dummy.next;

// TEMPLATE D — REVERSE IN GROUPS OF K (LC 25) — recursive, reads clean
ListNode reverseKGroup(ListNode head, int k) {
    ListNode node = head;
    for (int i = 0; i < k; i++) { if (node == null) return head; node = node.next; }  // enough?
    ListNode prev = reverseKGroup(node, k), curr = head;   // reverse the REST first
    for (int i = 0; i < k; i++) { ListNode nx = curr.next; curr.next = prev; prev = curr; curr = nx; }
    return prev;
}

The two things that go wrong

1. Losing the rest of the list. curr.next = prev destroys the forward link — so save next first, always. That’s why the order of the four lines never changes.
2. Returning head. After a reversal or a head deletion, head is no longer the head. Return prev (Template A) or dummy.next (Templates B/C).

When to use a dummy node

Whenever the answer’s first node might differ from the input’s first node: deletions, merges, partitions, “remove Nth from end”, sub-list reversal. It costs one allocation and removes every if (head == null) / if (removing the head) special case.

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Reverse a linked list” (fully or partially)
• “Reverse between position m and n”
• “Reverse in groups of K”
• “Swap nodes in pairs”
• Any problem requiring pointer direction changes

The Algorithm (Pseudocode)

prev = null
current = head

while (current != null):
    next = current.next     // save next
    current.next = prev     // reverse pointer
    prev = current          // advance prev
    current = next          // advance current

return prev  // new head

The ‘Trick’ to Know

• You need three pointers: prev, current, and next. Forgetting to save next before overwriting current.next loses the rest of the list.
• For partial reversal (reverse between m and n), you need to save the node before position m and the node at position m (which becomes the tail of the reversed section).

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Reverse Linked List - LC 206

Brute Force: Stack - O(n) time, O(n) space

class Solution {
    public ListNode reverseList(ListNode head) {
        Deque<Integer> stack = new ArrayDeque<>();
        ListNode current = head;

        while (current != null) {
            stack.push(current.val);
            current = current.next;
        }

        current = head;
        while (current != null) {
            current.val = stack.pop();
            current = current.next;
        }

        return head;
    }
}

Optimal: Iterative In-place - O(n) time, O(1) space

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

        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        return prev;
    }
}

Recursive Version - O(n) time, O(n) space (call stack)

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;
    }
}

Java Architecture Insights

• ArrayDeque over Stack: Stack extends Vector (synchronized, thread-safe overhead). ArrayDeque is faster for single-threaded use.
• Iterative vs. Recursive: Iterative is preferred in interviews for O(1) space. Recursive is elegant but risks StackOverflowError for very long lists (default JVM stack ~512KB).
• Modifying values vs. pointers: The stack approach modifies values (cheating in interviews). True reversal modifies the next pointers.

---

3. Mental Model & Visualization

ASCII Diagram (1 → 2 → 3 → null)

Start:   prev=null  curr=1→2→3→null

Step 1:  null ← 1   curr=2→3→null    prev=1
Step 2:  null ← 1 ← 2   curr=3→null  prev=2
Step 3:  null ← 1 ← 2 ← 3   curr=null prev=3

Return prev = 3 → 2 → 1 → null

Senior Mental Trigger

“Reverse linked list = save next, flip pointer, advance both.”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 206	Reverse Linked List	Easy
LC 21	Merge Two Sorted Lists	Easy
LC 234	Palindrome Linked List	Easy
LC 83	Remove Duplicates from Sorted List	Easy
LC 160	Intersection of Two Linked Lists	Easy

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 92	Reverse Linked List II (m to n)	Medium
LC 25	Reverse Nodes in k-Group	Hard
LC 24	Swap Nodes in Pairs	Medium
LC 143	Reorder List	Medium
LC 61	Rotate List	Medium

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
Stack	O(n)	O(n)	Extra space for all values
Iterative	O(n)	O(1)	Three pointers only
Recursive	O(n)	O(n)	Call stack space