leetcode 21. 合并两个有序链表（可进阶）

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

🧡 算法分析

此题是经典的二路归并算法

当头节点需要特判时，增加一个虚拟节点容易些，另外这题是在后面添加节点，需要一个尾节点记录信息

算法步骤:

1. new一个虚拟节点，因为需要在链表尾部插入元素，就需要增加一个尾节点记录信息
2. 遍历两个链表，当链表不为空时，将小的元素放入到新的链表中，直到其中一个链表为空
3. 将剩余不空的链表部分直接添加到链表后面

参照 23. 合并K个升序链表， 解法更加具有普适性，可进阶到K个升序链表的合并
代码实现（二）

💚 代码实现

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 经典的二路归并算法
        // 当头节点需要特判时，增加一个虚拟节点容易些，另外这题是在后面添加节点，需要一个尾节点记录信息
        auto dummy = new ListNode(-1), tail = dummy;

        while(list1 && list2) 
        {
            if(list1->val < list2->val) tail->next = list1, tail = tail->next, list1 = list1->next;
            else tail->next = list2,tail = tail->next, list2 = list2->next;
        }

        if(list1) tail->next = list1;
        if(list2) tail->next = list2;

        return dummy->next;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

💚 代码实现（二）

class Solution {
public:
    struct Cmp {
        bool operator() (ListNode* a, ListNode* b)
        {
            return a->val > b->val;
        }
    };

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 经典的二路归并算法
        // 当头节点需要特判时，增加一个虚拟节点容易些，另外这题是在后面添加节点，需要一个尾节点记录信息
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
        auto dummy = new ListNode(-1), tail = dummy;

        if(list1) heap.push(list1);
        if(list2) heap.push(list2);

        while(heap.size())
        {
            auto p = heap.top();
            heap.pop();

            tail = tail->next = p;
            if(p->next) heap.push(p->next);
        }

        return dummy->next;
    }
};

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

执行结果：

💙 时间复杂度分析

其中遍历一次， 时间复杂度为O(n)

算法二的时间复杂度分析参考 23. 合并K个升序链表

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！