Merge Two Sorted Lists — The Dummy-Head Pattern

This is rated Easy and is one of the cleanest demonstrations of the dummy-head pattern. The same trick reappears in Merge k Sorted Lists, Add Two Numbers, and Partition List.

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

Intuition

A naive approach collects all values into an array, sorts, and rebuilds — O((n+m) log (n+m)) and ignores the fact that inputs are already sorted.

The optimal idea is the merge step of merge sort directly on the linked-list nodes, guided by a dummy head. The dummy provides a stable anchor so we never have to special-case the first append. tail always points to the last node of the merged list so far. Each loop iteration picks the smaller current head, attaches it, and advances. When one list is exhausted, the other is already sorted, so we splice it on as a tail.

The recursive form reads like a definition: merge of two non-empty lists is the smaller head followed by the merge of the rest.

Explanation with Example

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

Step 1: Both heads are 1. Use <=, attach list1’s node. list1 advances to 2.

Step 2: Compare 2 and 1. Attach the 1 from list2. 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 empty; loop ends.

list1:   1 -> 2 -> 4
list2:   1 -> 3 -> 4

dummy -> 1(L1) -> 1(L2) -> 2(L1) -> 3(L2) -> 4(L1) -> 4(L2)
                                                    ^
                                                   tail

return dummy.next

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

Code

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

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

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

class ListNode {
    int val; ListNode next;
    ListNode(int val) { this.val = val; }
}

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
            else { tail.next = l2; l2 = l2.next; }
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

struct ListNode {
    int val; ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (l1 && l2) {
            if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; }
            else { tail->next = l2; l2 = l2->next; }
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

Edge Cases

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

Complexity Analysis

Iterative:

• Time: O(n + m). Each node visited 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 is a stable anchor, tail is the last merged node, each step picks the smaller head and advances. No allocation, just rewiring. Stability comes from the <= comparison. The recursive form is the same logic written declaratively. Mention that this same merge step generalizes to Merge k Sorted Lists via pairwise reduction or a min-heap.

Related Problems

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

Wrap up

Practice writing the iterative version without the dummy first to feel the awkwardness, then add it back. Once it is muscle memory, revisit Linked Lists Common Operations.