Pointers, dummies, and the middle

Reverse a linked list — iterative three pointers

Recognize it from — reverse the whole list, reverse a sublist, reverse in groups of k, or “the old head becomes the tail.” If they say “do it in place, O(1) extra,” they want the three-pointer walk, not a stack of nodes.

What it actually does — each node currently points forward. You flip that arrow so it points at the node you just left. You cannot overwrite cur.next until you have saved the rest of the list, or you lose the chain. Three names: prev is the reversed prefix, cur is the node you are flipping, nxt is the still-forward suffix.

When the loop ends, cur is null and prev sits on the original last node — that is the new head. The original head variable still names the old first node, which now has next == null (it is the tail). Return prev, not the old head.

ListNode reverseList(ListNode head) {
    ListNode prev = null;          // reversed prefix; empty at the start
    ListNode cur = head;           // node whose .next we are about to flip
    while (cur != null) {          // stop when the unreversed suffix is gone
        ListNode nxt = cur.next;   // save the rest — we are about to overwrite .next
        cur.next = prev;           // the actual reverse: this arrow now points backward
        prev = cur;                // the prefix grows by the node we just flipped
        cur = nxt;                 // walk onto the saved suffix
    }
    return prev;                   // prev is the original tail = new head
}

ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head; // 0 or 1 node: already reversed
    ListNode newHead = reverseList(head.next);          // reverse the suffix; newHead is the old tail
    head.next.next = head;  // the old successor now points back at us
    head.next = null;       // we become the tail of this suffix (cut the old forward link)
    return newHead;         // bubble the new head all the way up
}

Example 1 — simple

Input 1 → 2 → 3. Iterative loop only.

Answer: return prev = node 3. The list is 3 → 2 → 1.

Example 2 — every step

Input 1 → 2 → 3 → 4. Same iterative code. head still names node 1 the whole time; it is not the pointer you return.

Answer: return prev = node 4. Recursion on the same input: reverse(4) returns 4; then 3.next.next = 3 and 3.next = null gives 4 → 3; then 2 attaches behind 3; then 1 attaches behind 2. Same list, O(n) stack frames.

Merge two sorted lists — dummy head

Recognize it from — two (or k) lists already sorted; emit one sorted list. Merge k is the same idea with a heap of heads. Max-sum switching lists walks two sorted lists and jumps at shared values — dummy + two pointers still show up.

What it actually does — at every step you hold the remaining head of list A and list B. Whichever value is smaller (or equal — pick a consistent side) gets appended to the answer, and that list advances. A dummy node sits in front of the answer so the first append is identical to every later append. tail always names the last node already in the answer. When one list runs out, splice the rest of the other — it is already sorted.

ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0); // not part of the answer; dummy.next will be the head
    ListNode tail = dummy;            // last node in the merged list so far
    while (a != null && b != null) {  // both still have a candidate
        if (a.val <= b.val) {         // equal: take a (stable, either side is fine)
            tail.next = a;
            a = a.next;
        } else {
            tail.next = b;
            b = b.next;
        }
        tail = tail.next;             // the node we just attached is the new end
    }
    tail.next = (a != null) ? a : b;  // one list is empty — splice the other
    return dummy.next;
}

ListNode mergeTwoLists(ListNode a, ListNode b) {
    if (a == null) return b;
    if (b == null) return a;
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (a != null && b != null) {
        if (Integer.compare(a.val, b.val) <= 0) { // compare nodes, not a-b (overflow-safe habit)
            tail.next = a;
            a = a.next;
        } else {
            tail.next = b;
            b = b.next;
        }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    return dummy.next;
}

Example 1 — simple

A = 1 → 3, B = 2.

Answer: 1 → 2 → 3.

Example 2 — every step

A = 1 → 4 → 5, B = 1 → 3 → 4. This is two of the three lists from the merge-k notebook family. Equal values: this code takes A.

Answer: 1 → 1 → 3 → 4 → 4 → 5. Merge k does this among k heads with a min-heap instead of two pointers.

Middle of the list — fast / slow

Recognize it from — “return the middle node,” split a list for merge-sort or for a balanced BST, or detect a cycle (fast/slow is the same idea; cycle is a different stop condition).

What it actually does — slow moves one node, fast moves two. When fast can no longer take two steps, slow is in the middle. You do not count n first. On an even-length list this starting setup (slow = fast = head, loop while fast != null && fast.next != null) lands on the second middle — the start of the right half. Sorted-list-to-BST uses that mid as the root (or counts n and walks n/2; both are fine if you say which).

ListNode middle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) { // fast still has a two-step
        slow = slow.next;       // +1
        fast = fast.next.next;  // +2
    }
    return slow;                // even: second middle; odd: the unique middle
}

ListNode middleNode(ListNode head) {
    if (head == null || head.next == null) return head; // 0/1 node
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // 4 nodes → node 3 (second middle). First middle: start fast = head.next
}

Example 1 — simple

Five nodes: 1 → 2 → 3 → 4 → 5. Unique middle should be 3.

Answer: node 3.

Example 2 — every step

Even length: 1 → 2 → 3 → 4. Two middles: 2 (first) and 3 (second). This code returns the second middle.

Answer: node 3 (second middle). If they want the first middle, start fast = head.next or stop when fast.next.next == null. Say which before you type.

See also on this topic

Merge two is the inner loop of merge k. Reverse is the inner loop of reverse-k. Fast/slow mid is how a sorted list becomes a balanced BST. Max-sum switching lists is a two-list walk with a dummy — different rule (pick the better segment between shared nodes), same pointer hygiene. None of these is a Job 10454435 forecast.