21 - Merge Two Sorted Lists

Problem

You are given the heads of two sorted linked lists list1 and list2. Splice the two lists together 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.

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

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

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

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

Approach

Both lists are already sorted, so the smallest node left anywhere is always one of the two heads. Compare them, attach the smaller one to the end of the answer, and move that list forward. Repeat until one list runs out and attached the left over list at the end.

list1 = [1,2,4], list2 = [1,3,4]

dummy                      1 vs 1  take list1
dummy -> 1                 2 vs 1  take list2
dummy -> 1 -> 1            2 vs 3  take list1
dummy -> 1 -> 1 -> 2       4 vs 3  take list2
dummy -> 1 -> 1 -> 2 -> 3  4 vs 4  take list1
dummy -> 1 -> 1 -> 2 -> 3 -> 4     list1 empty, attach [4]
dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while(list1 && 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 ? list1 : list2;
        return dummy.next;
    }
};

• time: O(n + m) - each node is attached once
• space: O(1) - the nodes are reused, only dummy and tail are new