In-Place Reversal of a Linked List: The 3-Pointer Dance Every Interviewer Expects

Scenario context

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.

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…

This walkthrough focuses on Linked List Anatomy: Why You Cannot Just Index Backward.

Before making a design choice, clarify:

• 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.
• In a singly linked list, the edges are one-directional.

Concepts in play: jvm-internals-and-garbage-collection, stack-and-queue-data-structures, database-indexing, api-gateway

Stage 1 — 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.

Observable outcome: 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.

Stage 2 — 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.
• 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 ).

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

Observable outcome: 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 ).

Stage 3 — 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 i…
• • 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).

Observable outcome: 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).

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

• The new head is always prev when curr becomes null .

flowchart TD
    A[Initial: prev=null, curr=1, 12345] --> B[Save: next = curr.next = 2]
    B --> C["Flip: curr.next = prev (1null)"]
    C --> D[Advance: prev=1, curr=2]
    D --> E[Save: next = curr.next = 3]
    E --> F["Flip: curr.next = prev (21)"]
    F --> G[Advance: prev=2, curr=3]
    G --> H[Save: next = curr.next = 4]
    H --> I["Flip: curr.next = prev (32)"]
    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: 54321null]

Observable outcome: The new head is always prev when curr becomes null .

Stage 5 — 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…
• Protocol buffer streaming (gRPC, Netty) often builds linked chunks of bytes during serialization.

Observable outcome: Protocol buffer streaming (gRPC, Netty) often builds linked chunks of bytes during serialization.

Stage 6 — 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.
• 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.
• 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…

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

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

Observable outcome: 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…

End-to-end outcome

After working through the stages, you should be able to explain:

• • 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 .

Alternatives considered

Iterative vs Recursive Reversal: When Each Approach Fits

Both approaches visit every node once and produce identical results.

Failure and degraded modes

The source does not isolate a separate failure mode. Limits that matter for the scenario are called out in the stage decisions above.