Merge Two Sorted Lists

You are given the heads of two sorted linked lists, list1 and list2.

Merge them into one sorted list. The new list should be made by splicing together the nodes of the first two lists. Return the head of the merged list.

Constraints:

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

Brute Force

Put all the values in one array, sort it, and build a new list from it.

1. Walk through list1 and copy every value into an array.
2. Walk through list2 and copy every value into the same array.
3. Sort the array.
4. Build a new list from the sorted array, one node per value.

This works, but it ignores the fact that both lists are already sorted. We sort from scratch, and we also create brand new nodes instead of splicing the old ones.

class Solution {
    public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        vector<int> values;

        while (list1 != nullptr) {
            values.push_back(list1->val);
            list1 = list1->next;
        }

        while (list2 != nullptr) {
            values.push_back(list2->val);
            list2 = list2->next;
        }

        sort(values.begin(), values.end());

        ListNode* dummyHead = new ListNode(0);
        ListNode* tail = dummyHead;

        for (int value : values) {
            tail->next = new ListNode(value);
            tail = tail->next;
        }

        return dummyHead->next;
    }
};

• Time: O((m + n) log(m + n)). Sorting all values is the slow part.
• Space: O(m + n). We store every value and build new nodes.

Optimal Approach: Two Pointers with a Dummy Node

Both lists are already sorted. So the smallest remaining value is always at the front of one of the two lists. We compare the two fronts, take the smaller one, and repeat.

1. Create a dummy node and a pointer tail that points to it. The dummy gives us a fixed starting point, so the first node needs no special case.
2. Loop while both list1 and list2 have nodes.
3. Compare list1.val and list2.val. Attach the smaller node after tail, and move that list forward.
4. Move tail to the node we just attached.
5. When one list runs out, attach the rest of the other list in one step. It is already sorted.
6. Return dummyHead.next, which skips the dummy node.

We only change next pointers. No new nodes are created.

class Solution {
    public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* tail = dummyHead;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }

            tail = tail->next;
        }

        if (list1 != nullptr) {
            tail->next = list1;
        } else {
            tail->next = list2;
        }

        return dummyHead->next;
    }
};

Dry Run

Take list1 = [1,2,4] and list2 = [1,3,4].

1Start: tail = dummy, merged = (empty)
2 
3Step | list1 front | list2 front | Pick          | Merged so far
4-----|-------------|-------------|---------------|------------------
5  1  |  1          |  1          | list1 (1<=1)  | 1
6  2  |  2          |  1          | list2 (1)     | 1 -> 1
7  3  |  2          |  3          | list1 (2)     | 1 -> 1 -> 2
8  4  |  4          |  3          | list2 (3)     | 1 -> 1 -> 2 -> 3
9  5  |  4          |  4          | list1 (4<=4)  | 1 -> 1 -> 2 -> 3 -> 4
10 
11After step 5: list1 = null, list2 = [4]. The loop stops.
12Attach the rest of list2: ... -> 4
13 
14Return: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Why Does This Work?

Imagine two queues of people, and each queue is already sorted by height, shortest first. You want one queue sorted by height.

• Look at the first person in each queue.
• The shorter of the two is shorter than everyone left in both queues, because each queue is sorted.
• So that person goes next in the new queue.
• Repeat.

We never need to look past the front of a queue. That is why we only compare two values each step.

Why attach the leftover list in one step?

• When one list is empty, the other list still has nodes.
• That list is already sorted.
• Every node in it is greater than or equal to everything we already placed. If one was smaller, we would have picked it earlier.
• So we can attach the whole rest at once.

Why the dummy node? Without it, we must handle "what is the head?" as a special case. With it, the first node is attached the same way as every other node.

Why <= and not <? With equal values, either choice is correct. Using <= takes from list1 first, which keeps the merge stable.

Why This Is Better Than Brute Force

• The brute force sorts from scratch, which costs O(log n) extra work per element. We use the fact that the lists are already sorted, so one pass is enough.
• Time drops from O((m + n) log(m + n)) to O(m + n).
• The brute force builds all new nodes. We just re-link the existing nodes, so extra space drops from O(m + n) to O(1).
• This matches what the problem asks: splice the nodes of the two lists together.

Complexity

How to Explain It in an Interview