21 - Merge Two Sorted Lists

Difficulty: Easy | Pattern: Linked List / Two Pointers | Company tags: Amazon, Microsoft, Google, Facebook

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.

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]

Approach: Iterative with Dummy Node — O(m+n)

Key insight: Use a dummy head node to avoid special-casing the empty head. Compare the two current nodes, attach the smaller one, and advance that pointer.

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

def mergeTwoLists(list1, list2):
    dummy = ListNode(0)
    current = dummy
    
    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    # Attach remaining nodes (at most one list has nodes left)
    current.next = list1 or list2
    
    return dummy.next

Algorithm Flow

Dry Run

list1 = 1→2→4, list2 = 1→3→4

Step	list1	list2	chosen	result so far
1	1→2→4	1→3→4	list1 (1 lte 1)	dummy→1
2	2→4	1→3→4	list2 (1 lt 2)	→1→1
3	2→4	3→4	list1 (2 lt 3)	→1→1→2
4	4	3→4	list2 (3 lt 4)	→1→1→2→3
5	4	4	list1 (4 lte 4)	→1→1→2→3→4
6	None	4	attach list2	→1→1→2→3→4→4

Result: [1,1,2,3,4,4] ✓

Recursive Approach

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

Elegant but uses O(m+n) stack space — avoid for very long lists.

Edge Cases

• Both empty → return None
• One empty → return the other (handled by current.next = list1 or list2)
• All values equal → correct order maintained (stable: list1 chosen when equal)
• One list much longer → remaining nodes attached in O(1)

Complexity

Approach	Time	Space
Iterative	O(m+n)	O(1)
Recursive	O(m+n)	O(m+n) stack

Note: The current.next = list1 or list2 line is O(1) — we just reattach existing nodes, not copy them. This is in-place splicing.

Key Terms

Term	Definition in this problem's context
Dummy node	A placeholder head node that removes the need to special-case which list contributes the first node of the merged result.
Two pointers	list1 and list2 pointers each walk their own sorted list; only the smaller-valued node advances into the merged chain.
In-place splicing	Reusing existing nodes by relinking .next pointers instead of allocating new nodes — keeps space O(1) for the iterative version.
Tail pointer	The current pointer that always points to the last node attached to the merged list, so new nodes append in O(1).
Stable merge	When values are equal, list1's node is chosen first, preserving a deterministic, predictable output order.

FAQ

1. Can this be solved without extra space? Yes — the iterative approach is O(1) extra space because it only relinks existing nodes via the dummy/current pointers; no new nodes are allocated.

2. What happens if both input lists are empty? list1 and list2 are both None, the while loop never executes, and current.next = list1 or list2 evaluates to None, so dummy.next correctly returns None.

3. How would this change if the lists were unsorted? The two-pointer comparison relies on both inputs already being sorted; for unsorted lists you'd need to sort first (O(n log n)) or convert to a different strategy like collecting all values and sorting.

4. What's the follow-up interviewers usually ask? "Merge k sorted lists" (LeetCode 23) — extends this to merging multiple lists using a min-heap of size k or divide-and-conquer pairwise merging for O(N log k) time.

5. Why prefer the iterative solution over the recursive one in an interview? The recursive version is more concise but risks a stack overflow on very long lists (O(m+n) call stack depth), so the iterative dummy-node approach is the safer default answer.

Quick Revision

• Pattern: two pointers walking two sorted linked lists simultaneously.
• Use a dummy head node to avoid special-casing an empty result list.
• Maintain a current tail pointer; always attach the smaller of list1.val/list2.val.
• Advance only the pointer whose node was attached.
• When one list is exhausted, attach the remainder of the other directly (O(1), no traversal needed).
• Iterative version: O(m+n) time, O(1) space — the preferred interview answer.
• Recursive version: O(m+n) time, O(m+n) stack space — elegant but riskier for long lists.
• Equal values: list1's node is chosen first, giving a stable merge order.
• Return dummy.next, not dummy, since dummy itself is a placeholder.

Related Problems

• 88-MergeSortedArray — same merge-by-comparison idea applied to arrays instead of linked lists.
• LeetCode 23 Merge k Sorted Lists — direct generalization using a heap or divide-and-conquer pairwise merge (not present in this directory).
• LeetCode 148 Sort List — uses merge (as a subroutine) combined with merge sort on a linked list (not present in this directory).