Linked List Merge Technique

Description

Merging sorted linked lists means comparing the current heads again and again, and linking the smaller one onto the result. No new nodes are made; it's all rewiring, in one pass. With two lists, that's the merge step of merge sort. With k lists, the question is how to combine them. Folding them in one at a time is slow. Pairing them up round by round, or keeping the k heads in a min-heap, brings it down to O(N log k).

We'll go from simple to more technical:

1. The pattern: a dummy head, a tail pointer, take the smaller head.
2. A second flavor: merging k lists by pairing them up.
3. Where merging sorted streams runs in production.
4. The bugs that drop nodes - a forgotten leftover, an unpaired list.

The approach

Start the result with a dummy node and keep tail, its last node. Each round, compare the two lists' current heads. Link the smaller one after tail, and move along that list. When one list runs out, the other's remaining nodes are already sorted and all larger, so link the whole rest at once.

Merging 2 -> 5 -> 9 with 3 -> 4 -> 10:

ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (list1 != null && list2 != null) {
    if (list1.val <= list2.val) { tail.next = list1; list1 = list1.next; }
    else                        { tail.next = list2; list2 = list2.next; }
    tail = tail.next;
}
tail.next = (list1 != null) ? list1 : list2;   // attach whichever list still has leftovers
return dummy.next;

def merge_two(list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
    dummy = ListNode(0)
    tail = dummy
    while list1 is not None and list2 is not None:
        if list1.val <= list2.val:
            tail.next, list1 = list1, list1.next
        else:
            tail.next, list2 = list2, list2.next
        tail = tail.next
    tail.next = list1 if list1 is not None else list2   # attach whichever list still has leftovers
    return dummy.next

The dummy node keeps the loop simple. Without it, adding the very first node would need its own branch. At the end, dummy.next is the real head, whichever list it came from.

A second flavor: merging k lists by pairing them up

You could merge k lists one at a time into a growing result. But every merge rescans that growing result, so the total is O(N*k). Instead, merge the lists in pairs, using the two-list merge above. Each round halves the number of lists:

List<ListNode> current = new ArrayList<>(Arrays.asList(lists));
while (current.size() > 1) {
    List<ListNode> next = new ArrayList<>();
    for (int i = 0; i < current.size(); i += 2) {
        ListNode a = current.get(i);
        ListNode b = (i + 1 < current.size()) ? current.get(i + 1) : null;   // odd one out: no partner
        next.add(mergeTwo(a, b));
    }
    current = next;
}
return current.get(0);

def merge_k(lists: list[ListNode | None]) -> ListNode | None:
    current = list(lists)
    while len(current) > 1:
        nxt = []
        for i in range(0, len(current), 2):
            a = current[i]
            b = current[i + 1] if i + 1 < len(current) else None   # odd one out: no partner
            nxt.append(merge_two(a, b))
        current = nxt
    return current[0]

With 5 lists, the first round merges two pairs and carries the fifth list forward, leaving 3. The next rounds leave 2, then 1. Each round touches every node once, and there are about log k rounds, so the total is O(N log k). The list without a partner must be carried forward, not skipped. Merging it with null returns it unchanged.

Where you'll see it

This is the merge step of merge sort. It's also how two sorted streams, such as two pages of database results or two sorted log files, become one sorted stream without loading either fully. A log aggregator merging sorted logs from many servers usually keeps a min-heap of the current heads instead (see K-Way Merge Heap in Heaps). That's also O(N log k), in a single pass.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. When one list runs out, why is one assignment enough to attach the other, instead of walking it node by node?

2. In a pairing round with an odd number of lists, why merge the last list with null instead of skipping it?

3. Why is pairing up O(N log k) while folding one at a time is O(N*k)?

Key takeaways

• Merge two sorted lists in one pass: compare the heads and link the smaller one. A dummy node removes the first-node special case.
• When one list runs out, attach the rest of the other with one assignment.
• Merge k lists by pairing them up round by round: O(N log k), not O(N*k).
• Carry an unpaired list into the next round. Test with an odd number of lists.