Merging Two Sorted Linked Lists
Interleaving two ordered lists is the same two-finger scan that powers merge sort, but on pointers instead of indices — and the pointer version has an extra annoyance: choosing the head. The dummy node is the standard answer, and it is worth understanding as a general technique rather than as a one-off trick.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
struct Node {
int val;
Node* next;
};
Node* mergeLists(Node* a, Node* b) {
Node dummy;
dummy.next = NULL;
Node* tail = &dummy;
while (a != NULL && b != NULL) {
if (a->val <= b->val) { 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;
}
int main() {
Node n1, n2, n3, n4;
n1.val = 1; n1.next = &n3; n3.val = 4; n3.next = NULL;
n2.val = 2; n2.next = &n4; n4.val = 3; n4.next = NULL;
Node* m = mergeLists(&n1, &n2);
while (m != NULL) { cout << m->val << ' '; m = m->next; }
return 0;
}Splices existing nodes into one list without allocating — the dummy lives on the stack purely to give tail somewhere to start.
How it works, step by step
Nodes are relinked, not copied
The merge changes next pointers on the existing nodes rather than allocating new ones. That makes it O(1) space, and it also means both input lists are destroyed — the caller cannot use a or b afterwards.
The dummy removes the first-node special case
Without it, the first append has to set head instead of tail->next, which means an if on every iteration or a block of setup code before the loop. The dummy gives tail a valid node to write through from the very first step.
tail always points at the last node of the result
After each append, tail advances onto the node just added. Every new node is attached at tail->next, so the result grows at the end in O(1) with no traversal.
One line finishes the leftovers
When the loop ends, one list is exhausted and the other is not. Because the remainder is already sorted and already greater than everything appended so far, it can be attached wholesale with a single pointer assignment — no loop required.
<= keeps the merge stable
Taking from a when the values are equal preserves the relative order of equal elements across the two lists. This is the same detail that makes merge sort stable, and it is inherited directly from this step.
Complexity
Each node from both lists is examined and relinked at most once, and the only extra storage is the dummy plus two pointers; a recursive formulation is equally fast but consumes a stack frame per node.
Common bugs
Forgetting to attach the remaining list
Dropping the tail->next = (a != NULL) ? a : b line leaves the merged list truncated at whatever the loop last appended, and tail->next still points into the middle of an input list — or worse, at uninitialised memory. Every node after the shorter list's end simply disappears from the output.
Returning dummy.next after taking its address wrongly
Returning &dummy hands back a pointer to a stack object that dies when the function returns, so the caller reads freed memory. The dummy is scaffolding; only dummy.next is a real result. If you allocate the dummy with new instead, remember to delete it.
Not initialising dummy.next
If both input lists are empty the loop never runs and the final assignment sets dummy.next to b, which is NULL — fine. But any variant that returns early before that line reads an uninitialised pointer. Setting dummy.next = NULL up front costs nothing and closes the hole.
Advancing tail before setting tail->next
Reversing those two lines makes tail run ahead of the node it was supposed to link, producing a list that skips elements or ends abruptly. Stepping through node by node and watching where tail sits after each append makes the ordering requirement obvious.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why use a dummy node when merging linked lists?
It gives you a node to append to before the real head exists, so the loop body never needs a special case for the first element. Without it, every iteration would have to check whether the result list is still empty. At the end you return dummy.next and discard the dummy.
Does merging two sorted lists need extra memory?
No. The standard iterative merge only rewires the next pointers of the existing nodes, so it uses O(1) extra space regardless of list length. It does consume the input lists — after the call, the original head pointers no longer describe valid separate lists.
Why compare with <= instead of < when merging?
To keep the merge stable. When the two front values are equal, taking from the first list preserves the original relative order of equal elements. Using < takes from the second list instead and reverses them, which matters whenever the nodes carry payload beyond the sort key.
How is this related to merge sort?
It is exactly merge sort's combine step, expressed on pointers instead of array indices. Merge sort on a linked list uses this function directly: split the list in half, sort each half recursively, then merge. Because linked lists need no auxiliary array, merge sort is the natural choice for them.