Leetcode—23.合并 K 个升序链表【困难】-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode—23.合并 K 个升序链表【困难】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023每日刷题（八十三）

Leetcode—23.合并 K 个升序链表

Leetcode—23.合并 K 个升序链表【困难】,LeetCode刷题,leetcode,链表,算法,优先队列,最小堆,经验分享,c++

算法思想

用容量为K的最小堆优先队列，把链表的头结点都放进去，然后出队当前优先队列中最小的，挂上链表，，然后让出队的那个节点的下一个入队，再出队当前优先队列中最小的，直到优先队列为空。

实现代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](const ListNode* a, const ListNode* b) {
            return a->val > b->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;
        for(auto head: lists) {
            if(head) {
                pq.push(head);
            }
        }
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        while(!pq.empty()) {
            auto node = pq.top();
            pq.pop();
            if(node->next) {
                pq.push(node->next);
            }
            cur->next = node;
            cur = node;
        }
        return dummy->next;
    }
};

运行结果

Leetcode—23.合并 K 个升序链表【困难】,LeetCode刷题,leetcode,链表,算法,优先队列,最小堆,经验分享,c++
之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力！！！↖(▔▽▔)↗感谢支持！文章来源地址https://www.toymoban.com/news/detail-822536.html