leetcode 23. 合并K个升序链表

​
​

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

💜 题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

🧡 算法分析

此题是合并两个有序链表 的进阶版

同样可以用k个指针，然后按照合并两个有序链表的方式进行排序，这样的时间复杂度为O(nk)，n为链表中最大节点个数，k为链表的个数

但现在可以用一个优先队列数据结构找到每个链表的最小值，这样就能将找最小值得复杂度O(k)降为O(1), ，但是插入在优先队列（2叉树）的时间复杂度为O(logk)，所以总的时间复杂度为O(nlogk)

算法步骤:

1. 重载优先队列中的比较函数
2. 将链表指针存在优先队列中
3. 取出一个优先队列中顶部元素（就是最小元素），然后更新新链表的尾部
4. 判断取出链表元素后面是否还存在节点，如存在，继续放在优先队列中

💚 代码实现

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

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 优先队列中不传比较函数，就会默认按照地址来比较，我们这里是需要按照值来比较大小
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
        auto dummy = new ListNode(-1), tail = dummy;

        for(auto l : lists) if(l) heap.push(l);

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

            tail = tail->next = t;
            if(t->next) heap.push(t->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

执行结果：

💙 时间复杂度分析

如上分析，时间复杂度为：O(nlogk)

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