力扣(LeetCode)23. 合并K个升序链表(C++)

模拟k路归并

朴素思想，类比二路归并， $k$ 路归并多了一些参与比较的链表。我们可以在循环体内多一层循环，找到值最小的结点，插入答案链表的尾部。

朴素算法的时间复杂度 $O(k\times {\sum }_{i=0}^{k-1}list{s}_i.size())$ ， $k$ 是链表个数 ， $lis{t}_i.size()$ 是第 $i$ 个链表的长度。至少遍历每个结点一次，时间复杂度 $O({\sum }_{i=0}^{k-1}list{s}_i.size())$ 这是必须的。 找链表最小值 $O(k)$ ， 这一步可以用堆优化。

堆优化

建立小根堆，按链表值排序。将所有待比较结点加入堆，那么堆顶就是最小值 。

提示 : 优先队列默认大根堆 。 传入自定义的结构体，重载 “()” ， 按链表值 ， 建立小根堆 。 模板请背过。

class Solution {
public:
    typedef struct Cmp{
        bool operator () (ListNode* a,ListNode *b){
            return a->val>b->val;//按链表值,建立小根堆
        }
    }Cmp;
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode *,vector<ListNode*>, Cmp> heap;
        for(auto &l:lists) if(l) heap.push(l);
        auto dummy = new ListNode(-1);
        auto tail = dummy;
        while(heap.size()){
            auto l = heap.top();
            heap.pop();
            if(l->next) heap.push(l->next);
            tail->next = l;
            tail = tail->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

时间复杂度 $O(logk\times {\sum }_{i=0}^{k-1}list{s}_i.size())$ ，
用堆优化了查找最小值的时间复杂度 $O(logk)$ ， 至少遍历每个结点一次，时间复杂度 $O({\sum }_{i=0}^{k-1}list{s}_i.size())$ ， 总时间复杂度 $O(logk\times {\sum }_{i=0}^{k-1}list{s}_i.size())$

空间复杂度 $O(k)$ ， 堆中最多 $k$ 个结点 ， 空间复杂度 $O(k)$ 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC