The Dummy Node Trick That Makes Merging Sorted Linked Lists Trivial
The dummy-node pattern generalizes to nearly every linked-list insertion and deletion problem. Recognizing that the remaining chain can be attached whole — rather than node-by-node — cuts out unnecessary loops and signals fluency with pointer-based data structures.
Merging two ascending linked lists trips up beginners because the head node needs special treatment and the two lists rarely end at the same time. A dummy node sidesteps the head problem entirely: every new node attaches to a working cursor that starts at the dummy, so the real head is always `dummy.next`. The core loop compares the current nodes of both lists, links the smaller one, and advances the corresponding pointer. When one list runs out, the entire remaining chain can be attached in a single assignment because linked-list nodes already carry their successors. The result is an O(m+n) time, O(1) space solution that interviewers expect. The post walks through a verbose, beginner-friendly implementation with explicit remaining-node loops, then contrasts it with the one-line `cur.next = list1 || list2` finish that belongs in a tight interview answer.
The post’s beginner code uses two explicit while-loops to drain the remaining list, which is correct but redundant. That verbosity is pedagogically useful for learning pointer mechanics, yet the jump to a one-line tail attachment is what separates a working solution from an interview-ready one.
Many linked-list problems that feel edge-case-heavy — reversing sublists, removing duplicates, partitioning — collapse into uniform logic once a dummy node is introduced. The pattern is worth internalizing as a reflex.
The explanation that `cur.next = list1 || list2` works because a node’s `next` pointer already owns the rest of the chain is a small but crucial insight that often gets skipped in algorithm tutorials.