Why do sorted-list merge routines start with a dummy head node?

## The setting Two application servers each write an event log, and each log is already ordered by timestamp because events were appended as they happened. You want one combined timeline. Both logs are singly linked chains, so the merge should reuse the nodes that already exist and simply rewrite the links between them — not build a parallel structure. The loop that does this is the two-pointer merge: keep a cursor into each input, compare the two current timestamps, attach the earlier node to the end of the result, advance that cursor, repeat. ## The problem the sentinel solves "Attach to the end of the result" needs an end. On the first iteration there is no result yet, so the write has to go into a *head* variable instead of into some node's link field. Without a sentinel the loop body carries a branch — if the result is empty set `head`, otherwise set `tail.next` — or the routine hoists a special case before the loop that compares the two heads, sets `head`, advances that cursor, and only then enters the loop. Both versions work. Both are where hand-written merges break, because two variables (`head` and `tail`) must now be kept consistent along every path, including the paths where one input is empty from the start. A dummy head — a throwaway node whose payload is never read — removes the special case by making the result non-empty *before* the first comparison. `tail` starts at the dummy, and every iteration is the same two writes: - `tail.next = winner` - `tail = winner` There is no branch on "is this the first node", and no separate head variable to maintain: the head of the answer is whatever ended up in `dummy.next`, which the first iteration wrote there without knowing it was special. ## The remainder splice The loop condition is "both cursors are non-null" — the moment either input runs out, comparing is meaningless. What remains is a chain that is already sorted and already linked, so **one** write attaches all of it: `tail.next = whichever cursor is still non-null`. That single splice is the property that makes list merging cheap, and it is the step people forget. Two failure modes show up constantly: dropping the remainder entirely, which silently truncates the timeline; and writing a second loop that walks the leftover node by node, which is correct but pure waste, and is where the belief that merging must *move* n elements comes from. It moves none — it rewrites links. ## Ties between equal keys Comparing with `<=` rather than `<` decides which side wins when two events share a timestamp. With `<=`, nodes from the first input go first, so same-timestamp events keep the first server's ordering ahead of the second's. In log merging that is a real product decision, not a style choice, and it is worth saying out loud in an interview. ## Cost Time is O(n+m): each iteration consumes exactly one input node and each node is consumed once, plus the constant-time final splice. Auxiliary space is a fixed handful of references plus the one sentinel node — constant, with no per-element allocation. The sentinel changes neither bound; the claim that it "makes the merge O(1) space" is backwards, because the merge was already constant-space, sentinel or not. ## Returning the result Return `dummy.next`, not `dummy`. Returning the sentinel hands the caller a bogus first element with a meaningless timestamp — a bug that survives casual testing because the rest of the timeline looks perfect. Returning `dummy.next` is also what makes both-inputs-empty free: nothing was ever written into the dummy's link, so the caller gets an empty list with no extra test. ## The alternative The uniformity, not the node, is the real trick. If you can hold a reference to the *link field* to write next — initially the caller's head reference, then the link field of the node just attached — you get the same branch-free loop without allocating anything. That formulation is harder to narrate at a whiteboard, which is why the sentinel is the standard answer; but knowing that the sentinel is one way to buy uniformity, rather than a magic requirement, is what separates a memorized routine from an understood one.