Merge Two Sorted Lists: The Dummy Head and the One-Write Tail

Merge two sorted lists is the linked-list warm-up that quietly tests three things at once: whether you can re-point next fields without losing a node, whether you know the dummy-head trick, and whether you notice that the end of the merge is a single assignment rather than a loop. It is also the building block of merge sort on lists and of merging k sorted lists, so getting it clean pays off twice.

The problem it solves

You get the heads of two linked lists, each sorted in non-decreasing order. Return the head of one list that contains every node from both, still sorted. The usual phrasing adds that the result should be made by splicing the existing nodes together, not by copying values into new ones.

For 1 → 4 → 7 and 2 → 3 → 9 the answer is 1 → 2 → 3 → 4 → 7 → 9. Either input can be empty, and the two can have very different lengths.

The lazy approach, reading every value into an array, sorting it and building a fresh list, works but costs O((n + m) log(n + m)) time and allocates every node again. The merge does it in one pass with O(1) extra space.

The intuition

Both lists are already sorted, so the smallest remaining value is always at the front of one of them. You never need to look deeper than the two front nodes. Compare them, take the smaller, advance that list, repeat.

Two small ideas make the code short:

• A dummy head. The merged list needs a first node, and without a placeholder the first pick is a special case: you have to decide which head becomes the result before the loop starts. A throwaway node in front means every pick is the same pick, "attach it after tail". At the end you return dummy.next.
• The leftover chain is already done. When one list runs out, the other is still a sorted, linked chain whose every value is at least as large as anything already merged. One pointer write, tail.next = a or b, attaches all of it. There is nothing to copy and nothing to compare.

Using <= rather than < when the fronts are equal takes the node from the first list, so equal values keep their original relative order. That makes the merge stable, which is exactly what merge sort needs.

Watch it run

The animation merges 1 → 4 → 7 with 2 → 3 → 9, the same lists as the code. A dummy head waits below the two chains so the first node is not a special case. Only the two fronts are read: 1 against 2, and 1 is smaller, so tail.next points at that existing node and nothing is allocated. Then 4 against 2, 4 against 3, 4 against 9 and 7 against 9, each time splicing the smaller node onto the tail. After 7 goes, list a is empty. The rest of list b, just the 9, is already sorted and already linked, so one write takes all of it. The last frame counts it up: six values, five comparisons, zero new nodes. Only next fields changed.

The code

The lesson's merge, with a comparison counter and helpers to build and print lists:

class Node:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def build(vals):
    head = None
    for v in reversed(vals):
        head = Node(v, head)
    return head

def to_list(node):
    out = []
    while node:
        out.append(node.val)
        node = node.next
    return out

def merge(a, b):
    dummy = tail = Node(0)                 # placeholder: the first pick is not special
    compares = 0
    while a and b:
        compares += 1
        if a.val <= b.val:                 # <= keeps equal values in list a's order
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b                     # one write attaches the whole remainder
    return dummy.next, compares

head, compares = merge(build([1, 4, 7]), build([2, 3, 9]))
print(to_list(head), compares)                      # [1, 2, 3, 4, 7, 9] 5
print(to_list(merge(None, build([5, 6]))[0]))       # [5, 6]
print(to_list(merge(None, None)[0]))                # []

The recursive version is shorter and reads like the definition, but it uses one stack frame per node:

def merge_rec(a, b):
    if not a or not b:
        return a or b
    if a.val <= b.val:
        a.next = merge_rec(a.next, b)
        return a
    b.next = merge_rec(a, b.next)
    return b

print(to_list(merge_rec(build([1, 4, 7]), build([2, 3, 9]))))   # [1, 2, 3, 4, 7, 9]

try:
    merge_rec(build(list(range(0, 2000, 2))), build(list(range(1, 2000, 2))))
except RecursionError:
    print("RecursionError")                                     # RecursionError

Against a brute force that sorts the values, on 2,000 random pairs of lists, also checking that the result is made of exactly the original nodes:

import random

def node_ids(node):
    ids = set()
    while node:
        ids.add(id(node))
        node = node.next
    return ids

random.seed(18)
ok = True
for _ in range(2000):
    xs = sorted(random.randint(0, 9) for _ in range(random.randint(0, 8)))
    ys = sorted(random.randint(0, 9) for _ in range(random.randint(0, 8)))
    a, b = build(xs), build(ys)
    before = node_ids(a) | node_ids(b)
    head, c = merge(a, b)
    ok &= to_list(head) == sorted(xs + ys)
    ok &= node_ids(head) == before                  # same nodes, none allocated
    ok &= c <= max(len(xs) + len(ys) - 1, 0)
print(ok)                                           # True

The complexity

• Time: O(n + m). Every comparison places one node, and the loop stops as soon as either list is empty, so there are at most n + m - 1 comparisons.
• Space: O(1) extra for the iterative merge: one dummy node and two pointers. The recursive version needs O(n + m) stack, which is why a list of a few thousand nodes breaks Python's default recursion limit above.
• Merging k lists by pairing them up in rounds costs O(N log k) for N nodes in total, the same as a heap of the k fronts.

Where it goes wrong

• Advancing before attaching. a = a.next followed by tail.next = a attaches the wrong node and skips one. The tuple assignment in the code is safe because Python reads both right-hand values before writing either.
• Forgetting to advance tail. Every new node then overwrites the previous one's slot, and the result has two nodes.
• Copying the leftover node by node. It works, but it is a loop that does nothing the single write does not.
• Returning dummy instead of dummy.next. The answer then starts with the placeholder 0.
• Using < on equal values when stability matters, for example when the merge is part of a merge sort over records.

When it shows up in interviews

It is a standard easy question, often the first of two in a round, and it comes back as a step inside bigger ones: sort a linked list with merge sort, merge k sorted lists, or interleave two lists. Interviewers usually ask whether you allocated new nodes, what the dummy head buys you, and what the recursive version costs in stack space. A good follow-up answer mentions that the same two-front comparison merges two sorted arrays, with the difference that arrays need a buffer while lists only need pointer writes.

How to say it in an interview

"Both lists are sorted, so the next smallest value is always one of the two heads. I keep a dummy node and a tail pointer. Each step I compare the heads, attach the smaller one after the tail, advance that list and move the tail. When one list runs out, the other is already sorted and linked, so I attach it in one assignment. I use less-than-or-equal so the merge is stable. That is O(n + m) time and O(1) extra space, with no new nodes. The recursive version is shorter but uses a stack frame per node."

The k-list version is in merge k sorted lists, and the pointer handling it relies on is the same as in reversing a linked list.