TLDR: Reversing a linked list in O(1) space requires three pointers — prev, curr, and next. Each step: save next, flip curr.next to point backward, advance both prev and curr. Learn this once and you unlock four reversal variants that appear constantly in interviews.

---

📖 The O(1) Space Constraint That Forces the 3-Pointer Dance

Your interviewer says: "Reverse a linked list — but you can only use O(1) extra memory."

Most candidates freeze. Their instinct is to build a new list, push nodes onto a stack, or recurse (which uses O(n) stack space). None of those satisfy the O(1) constraint.

The trick is to reverse the arrows in place — you walk the list and repoint each .next field to the previous node rather than the next one. You need exactly three pointers to do this without losing your place in the list:

• prev — the node you just processed (initially null, becomes the new head)
• curr — the node you are currently reversing
• next — the node you would lose track of if you redirected curr.next before saving it

This three-pointer dance is a pattern that generalizes. Once you internalize it, variants like sub-list reversal, K-group reversal, and alternating-group reversal are incremental modifications — not separate algorithms to memorize.

---

🔍 Linked List Anatomy: Why You Cannot Just Index Backward

An array lets you swap arr[0] with arr[n-1], then arr[1] with arr[n-2], and so on. Linked lists have no random access — each node only knows its next node.

// The ListNode class used in all code examples in this post
public class ListNode {
    int val;
    ListNode next;

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

In a singly linked list, the edges are one-directional. Reversing the list means changing every edge from pointing forward to pointing backward. The only way to do this in-place without losing access to the rest of the list is to save curr.next before overwriting curr.next. That saved reference is the next pointer.

Without saving next, the moment you write curr.next = prev, you permanently lose the chain from curr onward. This is the most common mistake beginners make — the algorithm derails at the first node.

---

⚙️ The Three-Pointer Dance: Step-by-Step on a 5-Node List

Input: 1 → 2 → 3 → 4 → 5 → null

Goal: 5 → 4 → 3 → 2 → 1 → null

The four operations per step — always in this order:

1. next = curr.next — save the forward link before it is overwritten
2. curr.next = prev — reverse the edge (point backward)
3. prev = curr — advance prev
4. curr = next — advance curr using the saved forward link

When curr becomes null, prev is pointing at the last node processed — the new head (5).

Here is the complete Java solution for LeetCode 206 — Reverse Linked List:

public class ReverseLinkedList {

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next; // 1. save the forward link
            curr.next = prev;          // 2. reverse the edge
            prev = curr;               // 3. advance prev
            curr = next;               // 4. advance curr using the saved link
        }

        return prev; // prev is the new head
    }
}

---

🧠 Deep Dive: Pointer State Invariants and Edge Cases

Under the Hood: Internals of the Three-Pointer Update Sequence

The order of the four operations is not arbitrary — it is load-bearing:

• If you write prev = curr before curr.next = prev, then curr.next points to curr itself (a self-loop).
• If you write curr = next before next = curr.next, then next is undefined.
• The only safe order is: save next → flip edge → advance prev → advance curr.

After each complete step, the invariant holds:

• All nodes from the original head up to and including prev have been reversed (their .next points backward).
• All nodes from curr onward are still in their original forward-pointing state.
• prev.next and curr are disconnected — prev.next points to the previous prev, not to curr.

This invariant is why the algorithm is correct: when curr == null, the entire chain from the new head (prev) to the original head (now tail, with .next = null) is fully reversed.

Edge cases:

Performance Analysis: Time and Space Complexity

The iterative 3-pointer approach is strictly better than recursion on space. For very long lists (tens of thousands of nodes), recursive reversal risks StackOverflowError in Java; iterative does not.

---

📊 Pointer State After Each Step: 1 → 2 → 3 → 4 → 5 Traced

flowchart TD
    A["Initial: prev=null, curr=1, 1→2→3→4→5"] --> B["Save: next = curr.next = 2"]
    B --> C["Flip: curr.next = prev (1→null)"]
    C --> D["Advance: prev=1, curr=2"]
    D --> E["Save: next = curr.next = 3"]
    E --> F["Flip: curr.next = prev (2→1)"]
    F --> G["Advance: prev=2, curr=3"]
    G --> H["Save: next = curr.next = 4"]
    H --> I["Flip: curr.next = prev (3→2)"]
    I --> J["Advance: prev=3, curr=4"]
    J --> K["... continue for nodes 4 and 5 ..."]
    K --> L["curr = null — loop ends"]
    L --> M["Return prev = 5 as new head"]
    M --> N["Result: 5→4→3→2→1→null"]

Each step takes O(1). The loop runs n times total. The new head is always prev when curr becomes null.

---

🌍 Real-World Uses: Undo Stacks, Browser History, and Protocol Buffers

Undo/Redo stacks in editors store operations as linked list nodes. When a user hits "Undo All", reversing the list in-place lets the system replay operations in reverse order without allocating a new list.

Browser history is a doubly-linked list, but the in-place reversal pattern applies when back/forward traversal needs to be swapped — for example, when navigating history in a privacy-reset scenario where forward becomes backward.

Protocol buffer streaming (gRPC, Netty) often builds linked chunks of bytes during serialization. Before flushing to the wire, the byte chunk list may need reversal to restore correct ordering when chunks were prepended rather than appended.

Memory-constrained environments: Java's LinkedList deque implementation, Netty's CompositeByteBuf, and LRU cache eviction lists all use linked node structures where in-place pointer manipulation avoids allocation during hot paths.

Input / Process / Output for a browser-history reversal:

---

🧪 Four Reversal Variants: From Sub-List to Alternating Groups

Problem 1: Reverse a Linked List — Full Reversal (LeetCode 206)

Full solution shown in the ⚙️ section above.

Problem 2: Reverse a Sub-List — Positions p to q (LeetCode 92)

Advance to the node just before position p, then apply the 3-pointer reversal for exactly q − p + 1 nodes, then reconnect.

public class ReverseSubList {

    public ListNode reverseBetween(ListNode head, int p, int q) {
        if (head == null || p == q) return head;

        // Dummy node simplifies edge case where p == 1 (reversing from head)
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode beforeStart = dummy;

        // Step 1: advance to node just before position p
        for (int i = 1; i < p; i++) {
            beforeStart = beforeStart.next;
        }

        // Step 2: reverse q - p + 1 nodes starting at position p
        ListNode subListHead = beforeStart.next; // will become the tail of reversed segment
        ListNode curr = subListHead;
        ListNode prev = null;

        for (int i = 0; i <= q - p; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // Step 3: reconnect
        // subListHead.next now points to the first node after position q
        beforeStart.next = prev;        // connect before-segment to new head of reversed
        subListHead.next = curr;        // connect tail of reversed to after-segment

        return dummy.next;
    }
}

Trace on 1 → 2 → 3 → 4 → 5, p=2, q=4:

Problem 3: Reverse Every K-Element Sub-Group (LeetCode 25)

Check if at least k nodes remain; if yes, reverse them. Recurse on the tail.

public class ReverseKGroup {

    public ListNode reverseKGroup(ListNode head, int k) {
        // Check if there are at least k nodes remaining
        ListNode check = head;
        int count = 0;
        while (check != null && count < k) {
            check = check.next;
            count++;
        }
        if (count < k) return head; // fewer than k nodes — leave as-is

        // Reverse exactly k nodes
        ListNode prev = null;
        ListNode curr = head;
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // head is now the tail of the reversed group
        // Recursively reverse the rest and attach
        head.next = reverseKGroup(curr, k);

        return prev; // prev is the new head of this group
    }
}

For 1 → 2 → 3 → 4 → 5, k=2:

• Reverse [1,2] → 2 → 1, recurse on 3 → 4 → 5
• Reverse [3,4] → 4 → 3, recurse on 5
• 5 alone: count < k, return as-is
• Result: 2 → 1 → 4 → 3 → 5

Problem 4: Reverse Alternating K-Element Sub-Groups

Reverse k nodes, skip k nodes, repeat. The skip phase requires carefully tracking the tail of the skipped section for reconnection.

public class ReverseAlternatingKGroup {

    public ListNode reverseAlternatingKGroup(ListNode head, int k) {
        if (head == null) return null;

        // Phase 1: reverse first k nodes
        ListNode prev = null;
        ListNode curr = head;
        for (int i = 0; i < k && curr != null; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        // head is now the tail of the reversed segment; prev is the new sub-head

        // Phase 2: skip next k nodes (keep in original order)
        head.next = curr;           // connect reversed tail to start of skip window
        ListNode skipTail = head;   // track the last node of the skip window
        for (int i = 0; i < k && curr != null; i++) {
            skipTail = curr;
            curr = curr.next;
        }

        // Phase 3: recurse on remaining nodes
        if (curr != null) {
            skipTail.next = reverseAlternatingKGroup(curr, k);
        }

        return prev; // new head of this group
    }
}

For 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8, k=2:

• Reverse [1,2] → 2 → 1, skip [3,4], recurse on 5 → 6 → 7 → 8
• Reverse [5,6] → 6 → 5, skip [7,8], recurse on null
• Result: 2 → 1 → 3 → 4 → 6 → 5 → 7 → 8

Summary of the four variants:

---

⚖️ Iterative vs Recursive Reversal: When Each Approach Fits

Both approaches visit every node once and produce identical results. The difference is purely in space:

When recursive works fine: small lists, pedagogical clarity, or when K-group recursion depth is bounded by n/k (for large k, the depth is small).

When iterative is mandatory: production code, large lists, any environment where StackOverflowError is unacceptable (Java default stack is ~256 KB to 1 MB depending on JVM flags).

The interview default should be iterative — it demonstrates you understand the O(1) space requirement explicitly.

---

🧭 Choosing the Right Reversal Variant

---

🛠️ Java's LinkedList and Netty's LinkedList Internals: What In-Place Manipulation Looks Like in Production

java.util.LinkedList exposes Collections.reverse(list) which uses a list iterator and swaps values (not nodes). It does not do pointer reversal — it copies values between positions, which requires traversal to arbitrary positions and is O(n) with a large constant.

For true in-place node manipulation, production Java uses Netty's io.netty.util.collection.IntObjectHashMap internal linked chains, or the java.util.concurrent.ConcurrentLinkedDeque node unlinking pattern:

import java.util.Collections;
import java.util.LinkedList;

public class JDKReversal {

    public static void main(String[] args) {
        // JDK approach: reverses by swapping values, not pointers
        LinkedList<Integer> list = new LinkedList<>();
        list.addAll(java.util.Arrays.asList(1, 2, 3, 4, 5));
        Collections.reverse(list); // O(n), but mutates values not node links
        System.out.println(list); // [5, 4, 3, 2, 1]

        // The 3-pointer technique is needed when you work with raw ListNode objects
        // (as in LeetCode problems, custom data structures, or embedded systems)
        // rather than java.util.LinkedList
    }
}

Why the JDK does not use 3-pointer reversal for LinkedList: java.util.LinkedList is a doubly-linked list. Reversing it by swapping values between the two ends (using the two-pointer / iterator approach) is simpler to implement safely in a general-purpose library and avoids the pitfalls of node relinking. The 3-pointer technique is the canonical answer for singly-linked ListNode-style structures — exactly what interview problems use.

---

📚 Lessons from Getting the Pointer Order Wrong

Lesson 1 — Writing curr.next = prev before next = curr.next. This is the cardinal mistake. The moment curr.next is overwritten, you cannot recover the forward chain. Always save next first.

Lesson 2 — Returning curr instead of prev. When the loop exits, curr == null. Returning curr returns null. The new head is always prev. Burn this in.

Lesson 3 — Off-by-one in sub-list reversal. The loop for (int i = 0; i <= q - p; i++) reverses q − p + 1 nodes. If you write i < q - p, you reverse one fewer node and the list ends up partially reversed with a corrupted connection.

Lesson 4 — Forgetting the dummy node in sub-list reversal. When p == 1, there is no "node before position p" — beforeStart would need to point to something before the head. A dummy node new ListNode(0) with dummy.next = head eliminates this special case.

Lesson 5 — Not checking for fewer than k nodes in K-group. If the remaining tail has fewer than k nodes, LeetCode 25 specifies leaving them unreversed. Without the upfront count check, you reverse a partial group incorrectly.

---

📌 Summary: The In-Place Reversal Playbook

• Three pointers, four operations, always in this order: save next, flip curr.next, advance prev, advance curr.
• New head = prev when curr == null — never return curr.
• Dummy node eliminates the p == 1 edge case in sub-list reversal.
• O(1) space — no new nodes, no stack, no extra arrays. Only three scalar pointer variables.
• Recursion costs O(n/k) stack space for K-group variants. Prefer iterative for production.
• The most common bug: writing curr.next = prev before saving next. Saving next must always be the first operation.
• All four variants — full, sub-list, K-group, alternating K-group — share the same 4-line reversal inner loop.

One-liner to remember: Save next, flip the arrow, advance both pointers — repeat until curr is null, return prev.

---

📝 Practice Quiz

1. After one full iteration of the reversal loop on 1 → 2 → 3 → null, what are the values of prev and curr?

   • A) prev = null, curr = 1
   • B) prev = 1 (with 1.next = null), curr = 2
   • C) prev = 2, curr = 1 Correct Answer: B

2. In reverseBetween(head, p=2, q=4) on 1 → 2 → 3 → 4 → 5, after the reversal loop completes, subListHead (originally node 2) has its .next pointing to which node?

   • A) Node 3 — the reversal did not change node 2's forward link
   • B) null — the reversal loop set it to the initial prev which was null
   • C) Node 5 — the reconnect step sets subListHead.next = curr where curr = node 5 Correct Answer: B

3. In reverseKGroup(head, k=3) on a list of 5 nodes, what happens to nodes 4 and 5?

   • A) They are reversed into 5 → 4
   • B) They remain in their original order (4 → 5) because the remaining 2 nodes are fewer than k=3
   • C) They are discarded from the output Correct Answer: B

4. Open-ended challenge: The iterative 3-pointer reversal is O(1) space. However, reverseKGroup as written uses O(n/k) recursive call stack space. Rewrite reverseKGroup iteratively so that it uses only O(1) extra space for any value of k. What variables do you need to track across iterations to correctly reconnect segments?

---

🔗 Related Patterns and Posts

• Cyclic Sort: Find Missing and Duplicate Numbers in O(n) Time, O(1) Space
• Merge Intervals Pattern: Solve Scheduling Problems with Sort and Sweep
• Exploring Backtracking Techniques in Data Structures

---