21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

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

// Iteration
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // time: O(m + n); space: O(1)
    ListNode* dummy = new ListNode(-1), *pre = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            pre->next = l1;
            l1 = l1->next;
        } else {
            pre->next = l2;
            l2 = l2->next;
        }
        pre = pre->next;
    }
    if (l1) pre->next = l1;
    else if (l2) pre->next = l2;
    ListNode* res = dummy->next;
    delete dummy;
    return res;
}

// Recursion
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // time: O(m + n); space: O(m + n)
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}