Merge Two Sorted Lists

Posted on Edited on In Views:

21.Merge Two Sorted Lists

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

Merge the two lists in a 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:

img

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

Example 2:

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

Example 3:

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

个人解答：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* ans_list = new ListNode;
    ListNode* node = ans_list;
    while (list1 != nullptr && list2 != nullptr) {
        if (list1->val < list2->val) {
            node->next = list1;
            list1 = list1->next;
        }
        else {
            node->next = list2;
            list2 = list2->next;
        }
        node = node->next;
    }
    node->next = list1 == nullptr ? list2 : list1;//将未合并完的一个链表直接接在ans_list之后
    return ans_list->next;
}

递归法：

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) {
        return l2;
    } else if (l2 == nullptr) {
        return l1;
    } else if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}