Merge Two Sorted Lists

21. Merge Two Sorted Lists

分析

创建虚拟头节点
- 创建一个虚拟头节点 dummy，用于方便拼接新链表，同时维护一个指针 cur 指向结果链表的当前末尾
比较两个链表节点值
- 遍历 list1 和 list2，每次比较当前节点值，将较小值的节点接到 cur 的后面，并将对应链表的指针后移
拼接剩余节点
- 如果某个链表还有剩余节点（未遍历完），直接将其接到结果链表末尾
返回结果链表
- 返回虚拟头节点的下一个节点 dummy->next，即为合并后的升序链表

时间复杂度

遍历两个链表，最多比较 n + m 次，其中 n 和 m 分别为两个链表的长度，时间复杂度 O(m + n)

空间复杂度

空间复杂度 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution
{
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        // 创建虚拟头节点，简化操作
        ListNode *dummy = new ListNode();
        ListNode* cur = dummy;

        // 归并两个链表
        while (list1 && list2)
        {
            if (list1->val <= list2->val) // list1节点值较小
            {
                cur = cur->next = list1;  // 接入结果链表
                list1 = list1->next;      // list1指针后移
            }
            else                          // list2节点值较小
            {
                cur = cur->next = list2;  // 接入结果链表
                list2 = list2->next;      // list2指针后移
            }
        }

        // 拼接剩余的链表
        if (list1) cur->next = list1;
        if (list2) cur->next = list2;

        // 返回结果链表
        return dummy->next;
    }
};