Merge Two Sorted Lists — The Dummy Head Pattern Every Interview Expects

Problem Statement#

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Constraints:

• The number of nodes in both lists is in the range [0, 50]
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order

Example 1:

Input:  list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input:  list1 = [], list2 = []
Output: []

Example 3:

Input:  list1 = [], list2 = [0]
Output: [0]

Why This Problem Matters#

Merge Two Sorted Lists (LeetCode 21) is one of the most frequently asked problems in software engineering interviews. Amazon, Google, Microsoft, and virtually every company that asks linked list questions uses this problem or its harder variants (merge k sorted lists, sort list). It is Easy rated but exposes medium-to-hard concepts: pointer manipulation, the dummy node trick, and correct handling of unequal list lengths.

The reason interviewers love this problem is that it has exactly one well-known optimal approach — the dummy head merge pattern — but candidates who haven't practiced it will fumble the special cases. What happens when one list is exhausted? What if both lists are empty? Where exactly does the pointer cursor live? These are the questions that reveal preparedness.

At a higher level, merging sorted sequences is the core operation behind merge sort, external sort (used in databases for sorting data larger than RAM), and the merge step in k-way merge algorithms used in stream processing. Understanding this problem cold means you understand the most fundamental merge operation in computer science.

The recursive variant of this problem also appears in interviews as a follow-up, testing whether you can express the same logic through a recursive lens. Both forms are worth knowing.

The Core Insight#

Create a dummy node before the start of the result list. This dummy node serves as a sentinel that never changes and gives you a stable anchor. You keep a curr pointer that starts at the dummy and always points to the last node added to the result.

At each step, compare the heads of the two input lists. Whichever is smaller gets appended to the result and its list advances. When one list is exhausted, you simply attach the remaining non-null list to the end — no loop needed, because both input lists are already sorted.

The dummy node eliminates the special case of building the head of the result list. Without it, you need branching logic just to initialize. With it, every step is identical.

Visual Dry Run#

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

Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Solution (Optimal)#

Python#

def mergeTwoLists(list1, list2):
    dummy = ListNode(0)   # sentinel — its .next will be the answer
    curr = dummy          # cursor points to the last node added
 
    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1    # take from list1
            list1 = list1.next   # advance list1
        else:
            curr.next = list2    # take from list2
            list2 = list2.next   # advance list2
        curr = curr.next         # advance cursor
 
    # Attach whichever list still has nodes
    curr.next = list1 if list1 else list2
 
    return dummy.next  # skip the sentinel

Time complexity: O(m + n) — every node is visited exactly once.

Space complexity: O(1) — we reuse the existing nodes; no new nodes are allocated.

JavaScript#

var mergeTwoLists = function(list1, list2) {
    const dummy = new ListNode(0);
    let curr = dummy;
 
    while (list1 !== null && list2 !== null) {
        if (list1.val <= list2.val) {
            curr.next = list1;
            list1 = list1.next;
        } else {
            curr.next = list2;
            list2 = list2.next;
        }
        curr = curr.next;
    }
 
    curr.next = list1 !== null ? list1 : list2;
    return dummy.next;
};

Recursive variant (Python):

def mergeTwoLists(list1, list2):
    # Base cases
    if not list1:
        return list2
    if not list2:
        return list1
    # Smaller value becomes the head; recurse on the rest
    if list1.val <= list2.val:
        list1.next = mergeTwoLists(list1.next, list2)
        return list1
    else:
        list2.next = mergeTwoLists(list1, list2.next)
        return list2

Complexity:

Common Mistakes#

1. Not using a dummy node. Without a dummy, you need to handle the first node as a special case: "which list do I take from first to establish the head?" The dummy node makes every step identical and eliminates this branch.

2. Forgetting curr = curr.next inside the loop. If you attach curr.next = list1 but forget to advance curr, the cursor stays at the dummy node and every new node overwrites curr.next — you lose everything except the last node added.

3. Handling the remainder with a loop instead of a direct attach. After one list empties, the other list is already sorted. You don't need to loop through it — just set curr.next = remaining_list. Adding an unnecessary loop is a sign you haven't internalized the pattern.

4. Returning dummy instead of dummy.next. The dummy node is a sentinel with value 0 that doesn't belong in the answer. Always return dummy.next — the first real node of the merged list.

5. Mutating input lists unnecessarily. The optimal approach reuses existing nodes (splices them into the result) which is correct per the problem statement. But if an interviewer asks for a non-destructive merge, you need to create new nodes — clarify the requirement upfront.

Interview Tips#

1. State the approach before coding: "I'll use a dummy head as an anchor and a curr cursor. At each step I compare the two list heads and take the smaller. When one list is done I attach the rest."

2. Handle the empty list case explicitly in your explanation — even though the code handles it naturally, interviewers want to see you've thought about it.

3. Complexity analysis matters: State O(m+n) time and O(1) space before they ask.

4. Know the recursive version — it's elegant and shows you can think about the problem both ways. Interviewers often ask for it as a follow-up: "Can you write it recursively?"

5. Bridge to harder problems: If you finish early, volunteer: "This same pattern is the merge step in merge sort on linked lists (LC 148) and the core of merge k sorted lists (LC 23)."

Follow-up Questions#

Q: How does this extend to merging K sorted lists? For K lists, a min-heap (priority queue) gives O(n log k) time, where n is total nodes. You push the heads of all K lists into the heap and always pop the minimum. This is LeetCode 23.

Q: Can you sort a linked list using this merge? Yes — that's LeetCode 148 (Sort List). Use fast/slow pointers to split the list at the midpoint, recursively sort each half, then merge using this exact function. Time: O(n log n), Space: O(log n) for the call stack.

Q: What if you cannot modify the original lists? You would create new ListNode objects for each step instead of splicing existing ones. Time remains O(m+n), but space becomes O(m+n).

Q: What if the lists are not sorted? You would first sort them (O(n log n) each), then merge. Or you could concatenate and sort in O((m+n) log(m+n)). Clarify with the interviewer whether sorting is needed.

Q: Is there a way to do it with O(1) space and no dummy node? Yes — initialize the result head from whichever list has the smaller first element, then proceed iteratively. It works but requires more bookkeeping. The dummy node approach is universally preferred for clarity.

Key Takeaways#

• The dummy head sentinel eliminates all special-case branching when building the result list's head.
• After the loop, attach the remaining non-exhausted list with a single pointer assignment — no extra loop needed.
• Always return dummy.next, not dummy itself.
• The iterative approach is O(m+n) time and O(1) space — always state this explicitly.
• The recursive version is elegant but uses O(m+n) stack space — prefer iterative for large inputs.
• This merge operation is the foundation for merge sort on linked lists, merge k sorted lists, and external sorting algorithms.