21-合并两个排序的链表

LeetCode 21. Merge Two Sorted Lists

LeetCode-21

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

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

method 1: 迭代

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    ListNode *dummy = new ListNode(0);
    ListNode *head = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            head->next = l1;
            l1 = l1->next;
        }
        else {
            head->next = l2;
            l2 = l2->next;
        }
        head = head->next;
    }
    if (l1) head->next = l1;
    if (l2) head->next = l2;
    return dummy->next;
}

时间复杂度：$O(n+m)$，每个节点都要处理
空间复杂度：$O(1)$

method 2: 递归

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    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;
    }
}

时间复杂度：$O(n+m)$
空间复杂度：$O(n+m)$，递归栈的深度