LeetCode Merge Two Sorted Lists: The Dummy-Head Pattern

LeetCode 21 Merge Two Sorted Lists is rated Easy and is one of the cleanest demonstrations of the dummy-head pattern. The same trick reappears in problems like Merge k Sorted Lists, Add Two Numbers, and Partition List. Once you internalize it, you stop worrying about whether the result list is empty when you append the first node.

The Problem

You are given the heads of two sorted singly linked lists, list1 and list2. Splice them into a single sorted list by reusing nodes from both inputs, and return the new head.

Example:

Input:  list1 = 1 -> 2 -> 4
        list2 = 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Each list has between 0 and 50 nodes, and values fit in a 32-bit integer.

Brute Force

A naive method collects every value into an array, sorts it, and rebuilds the list.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_brute(list1, list2):
    values = []
    for head in (list1, list2):
        cur = head
        while cur:
            values.append(cur.val)
            cur = cur.next
    values.sort()

    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

This is O((n + m) log(n + m)) time and O(n + m) extra space. It ignores that the inputs are already sorted.

Optimal Solution

Use the merge step of merge sort directly on the linked-list nodes, guided by a dummy head.

def merge_two_lists(list1, list2):
    dummy = ListNode()
    tail = dummy

    while list1 and list2:
        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 else list2
    return dummy.next

The recursive form is even shorter and reads like a definition.

def merge_two_lists_recursive(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1
    if list1.val <= list2.val:
        list1.next = merge_two_lists_recursive(list1.next, list2)
        return list1
    list2.next = merge_two_lists_recursive(list1, list2.next)
    return list2

Walk Through an Example

Inputs: list1 = 1 -> 2 -> 4 and list2 = 1 -> 3 -> 4.

Step 1: Both heads are 1. Use <=, so attach list1’s node. tail now points to that 1, and list1 advances to 2.

Step 2: Compare 2 and 1. Attach the 1 from list2. tail advances; list2 is now 3 -> 4.

Step 3: Compare 2 and 3. Attach 2 from list1. list1 is now 4.

Step 4: Compare 4 and 3. Attach 3 from list2. list2 is now 4.

Step 5: Compare 4 and 4. Attach 4 from list1. list1 is now empty, so the loop ends.

Final step: append the rest of list2, which is 4. Return dummy.next, yielding 1 -> 1 -> 2 -> 3 -> 4 -> 4.

Edge Cases

• Both lists empty: dummy stays alone, tail.next is set to None, and we return None.
• One list empty: the while loop never executes; the final line attaches the non-empty list directly. This is the main reason the dummy head pays off.
• Equal head values: using <= keeps the merge stable, preserving the order from list1 first.
• Very long single list: O(n) traversal, no recursion stack worries with the iterative version.

Complexity Analysis

Iterative:

• Time: O(n + m). Each node is visited exactly once.
• Space: O(1) auxiliary because we splice existing nodes.

Recursive:

• Time: O(n + m).
• Space: O(n + m) for the call stack in the worst case.

How to Explain It in an Interview

Open with the invariant: the dummy head provides a stable anchor, and tail always points to the last node of the merged list so far. Each loop iteration picks the smaller of the two current heads, attaches it, and advances the corresponding pointer. When one list is exhausted, the other is already sorted, so we splice it on as a tail.

Highlight that no new nodes are allocated; we are rewiring existing ones. If asked about stability, mention that the <= comparison preserves the relative order of equal values from list1. If the interviewer asks about recursion, explain the base cases and that each call reduces the combined length by one, giving linear time.

If you have time, mention that this same merge step generalizes to Merge k Sorted Lists, where you can either reduce pairwise or use a min-heap.

Related Problems

• LeetCode 23 Merge k Sorted Lists, which generalizes this routine.
• LeetCode 148 Sort List, which combines merge sort with linked lists.
• LeetCode 2 Add Two Numbers, another dummy-head application.
• LeetCode 86 Partition List for splicing nodes by a predicate.

Wrap up

Merge Two Sorted Lists is a textbook dummy-head problem. Practice writing the iterative version without the dummy first to feel the awkwardness, then add the dummy back and see how much simpler the code becomes. Once it is muscle memory, revisit Linked Lists Common Operations and try Add Two Numbers or Partition List to reinforce the same pattern.