21. Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list by splicing their nodes together, and return its head.

Building a paper chain from two other chains, picking the smaller-valued link each time. Before you attach the first real link, you need a throwaway paperclip (dummy) to hold onto, since the chain doesn't exist yet.

current is your hand — starts on the paperclip, and after every attachment, slides forward onto whatever you just attached. If your hand never moves, you keep re-clipping new links onto the paperclip instead of onto the end of the growing chain, and everything before your hand becomes unreachable.

dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4
  ↑                              ↑
(never moves)              current ends up here

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode();
    ListNode current = dummy;

    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;   // the line I kept forgetting
    }

    // whichever list still has leftovers just gets attached wholesale
    if (list1 != null) {
        current.next = list1;
    }
    if (list2 != null) {
        current.next = list2;
    }

    return dummy.next; // NOT dummy, NOT current — the real head is right after dummy
}

This one took me several tries to actually get right, and looking back, I kept making the same category of mistake in different forms:

1. First I tried checking list1.val != null — forgot val is an int, and primitives can never be null. Should have been checking list1 != null (the node reference itself), not the value inside it.
2. Then I tried if (list1 && !list2) — treating a ListNode reference like a boolean, which isn't a thing in Java (no truthy/falsy checks like JS or Python).
3. Even after fixing the null checks, I only had one pointer (current) doing the job of two things: (a) remembering where the merged list starts, and (b) tracking where to attach the next node. Those need to be two separate variables — dummy (never moves) and current (moves every iteration).
4. Even after splitting those into two variables, I forgot the actual moving part: current = current.next. I attached nodes fine, but never moved current forward, so every new attachment silently overwrote the previous one and orphaned it in memory.

Honestly, #4 is the one that took the longest to click. I understood "attach a node" but not that the pointer doing the attaching also has to walk forward itself, or it just keeps stepping on its own work.

The bug, traced by hand

list1 = [1, 2, 4], list2 = [1, 3, 4]. Without current = current.next:

• Iteration 1: 1 < 1 false → dummy.next = list2's "1" node. current still = dummy.
• Iteration 2: 1 < 3 true → dummy.next = list1's "1" node. The node from iteration 1 is now unreachable — nothing points to it anymore. Same root idea as the x = x++ gotcha from OCA: writing to the same slot twice instead of advancing.

With the fix, current moves onto the newly attached node each time, so the next attachment writes to current.next — which is a fresh, unused slot — instead of overwriting the same one repeatedly.

Three lines per attachment, not two

I kept dropping down to two lines out of habit. The full set, every time:

1. current.next = <chosen node> — attach it
2. <sourceList> = <sourceList>.next — advance the list you took the node from
3. current = current.next — advance your own "where do I attach next" pointer

Missing #3 is subtle because the code still compiles and even runs — it just silently produces a broken, truncated result instead of throwing an exception. That's arguably worse than a compile error, because nothing tells you it's wrong except the actual output being incomplete.

Why return dummy.next and not dummy or current

• dummy — the paperclip itself, never a real part of the list. Returning it would hand back a list with a bogus 0 value glued to the front.
• current — by the time the loop ends, this is sitting at the last node attached, not the first. Returning it would only give back the tail end.
• dummy.next — the paperclip's .next field was set exactly once, on the very first attachment, and never touched again after that (only current kept moving). So dummy.next reliably points at the true head.

Java 8

Fine on Java 8 — just references, a while loop, and object creation. Nothing version-specific.

• Time: O(n + m) — walk each list once, total.
• Space: O(1) — only a few reference variables, no new list built from scratch.

• Can I explain, without looking, why current needs to move but dummy never does?
• What breaks if I return current instead of dummy.next?
• What breaks if I forget the leftover-list handling after the loop — walk through an example where list1 empties out early with list2 still having 3 nodes left.
• Try writing the recursive version and figure out why it doesn't need a dummy node at all (this connects to the same question I skipped on LC 206).