Merge Two Sorted Lists

Merging two sorted sequences is the heart of merge sort, of combining sorted log files, and of joining sorted database results. On linked lists it is also the cleanest use of the dummy-head-and-tail template: two sorted chains go in, one sorted chain comes out, and no new node is created.

The whole problem rests on one observation about sorted input: the smallest value not yet placed is always at the front of one of the two lists. You never need to look further than two nodes.

The problem

You are given the heads of two lists, each sorted in non-decreasing order. Merge them into one sorted list by relinking their nodes, and return its head.

• 1 → 4 → 6 and 2 → 3 → 6 → 8 → 1 → 2 → 3 → 4 → 6 → 6 → 8.
• An empty list and 0 → 0.
• Two empty lists → an empty list.

Constraints: each list has 0 to 10⁴ nodes; values between −10⁴ and 10⁴.

Clarifying questions

• Should I reuse the existing nodes? Yes — splice them; do not create new ones.
• Can values repeat, across or within the lists? Yes. Equal values may appear in either order, but keeping the first list's node first (a stable merge) is a good habit.
• Can either list be empty? Yes, and both can.
• Ascending order? Yes, both inputs and the output.

Approach 1: collect, sort, rebuild

Pour every value into one array, sort it, and build a new list.

1def merge_two_lists_sort(first: ListNode | None, second: ListNode | None) -> ListNode | None:2    """Pour both lists into an array, sort, rebuild."""3    values = []4    for node in (first, second):5        while node is not None:6            values.append(node.value)7            node = node.next8    values.sort()9    dummy = ListNode()10    tail = dummy11    for value in values:12        tail.next = ListNode(value)13        tail = tail.next14    return dummy.next

Time: O((m + n) log(m + n)) for the sort. Space: O(m + n) for the array and the new nodes.

At 2 × 10⁴ values this runs quickly, so speed is not the real objection. It throws away the fact that both inputs are already sorted, which is the entire point of the problem, and it creates new nodes when you were asked to relink the old ones. An interviewer will immediately ask you to use the sortedness.

The key insight

Both lists are sorted, so each list's smallest remaining value is at its head. The smallest remaining value overall must therefore be the smaller of the two heads. Take that node, attach it to the output, and advance in the list it came from. Repeat.

When one list runs out, the other list's remaining nodes are already sorted, already linked to each other, and all at least as large as everything placed so far. So you attach the whole remainder with one pointer assignment — no loop.

The output list starts empty, which normally forces a special case: "if this is the first node, set the head; otherwise append to the tail." A dummy node removes it. The tail starts at the dummy, every append is tail.next = node, and the answer is dummy.next.

Approach 2: splice with a dummy head

1def merge_two_lists(first: ListNode | None, second: ListNode | None) -> ListNode | None:2    """Splice nodes in order behind a dummy head. O(m + n) time, O(1) space."""3    dummy = ListNode()4    tail = dummy5    while first is not None and second is not None:6        if first.value <= second.value:     # <= keeps ties in first-list order7            tail.next = first8            first = first.next9        else:10            tail.next = second11            second = second.next12        tail = tail.next13    tail.next = first if first is not None else second   # attach the leftover run14    return dummy.next

Dry run on 1 → 4 → 6 and 2 → 3 → 6 → 8. "Merged so far" is the chain from dummy.next up to tail.

At step 5 the heads are equal and <= takes the first list's 6, so the merge is stable. Then first is empty and the loop stops. The last line attaches 6 → 8 from the second list in one write.

Why bother with <= rather than <? Both produce a sorted list. But <= takes the first list's node when values tie, so equal values keep the order they had across the two inputs. That property, stability, is what makes merge sort stable, and it matters when nodes carry more than their sort key — two orders with the same price, say, should stay in their original order.

One subtle point: a node you attach still has its old next pointer, which may point back into its original list. That is harmless. The next iteration, or the final attach, overwrites tail.next, so every stale link is replaced before the function returns.

Time: O(m + n) — each node is attached once. Space: O(1) — the dummy and two pointers; no new list nodes.

Approach 3: recursion

1def merge_two_lists_recursive(first: ListNode | None, second: ListNode | None) -> ListNode | None:2    if first is None:3        return second4    if second is None:5        return first6    if first.value <= second.value:7        first.next = merge_two_lists_recursive(first.next, second)8        return first9    second.next = merge_two_lists_recursive(first, second.next)10    return second

It reads like the definition: the merged list is the smaller head, followed by the merge of everything else. It is elegant and short, but each node adds a stack frame, so it is O(m + n) space and fails on lists of a few thousand nodes in CPython. Mention it; submit the iterative one.

Edge cases

• One or both lists empty: the loop never runs, and the last line attaches whichever list is not empty (or None). No special case.
• One list much shorter: [5] and [1, 2, 3, 4, 6, 7] — the loop runs until 5 is placed, then attaches 6 → 7 at once.
• All values equal: <= always takes from the first list, so it drains the first list and then attaches the second. Still correct and stable.
• Negative values: comparisons handle them; nothing changes.

Follow-ups

• Merge k sorted lists: keep the k current heads in a min-heap and pop the smallest each time: O(N log k) for N nodes in total. Or merge the lists in pairs, halving the count each round, which is also O(N log k). The Heaps section covers it.
• Sort a linked list (merge sort): split the list at its middle, sort each half recursively, and merge them with this function. O(n log n) time, and the only sort that suits a singly linked list well.
• Merge in descending order, or merge while removing duplicates: the same loop; flip the comparison, or skip a node whose value equals tail.value.