首页 / 更多教程 / 【Leetcode】合并K个排序链表

【Leetcode】合并K个排序链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【Leetcode】合并K个排序链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1001字，纯文字阅读大概需要2分钟。

内容图文

题目链接：合并K个排序链表


题意：合并k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。


题解：这题的前身是合并两个排序链表。在剑指里有写。可以点击链接查看。。

这个题，最好就是用小顶堆，O(nlog(K))。用c++的优先队列可以解决这个小顶堆。

把每个节点丢进优先队列，然后以出队列的顺序作为新链表顺序


代码： 

             1
            /*
            *

             2
             * Definition for singly-linked list.

             3
             * struct ListNode {

             4
             *     int val;

             5
             *     ListNode *next;

             6
             *     ListNode(int x) : val(x), next(NULL) {}

             7
             * };

             8
            */
             9
            class
             Solution {

            10
            public
            :

            11
            //
            优先队列重载cmp函数
            12
            struct
             cmp{

            13
            bool
            operator()(ListNode* a,ListNode* b){
14return a->val > b->val; //小顶堆15        }
16    };
1718     ListNode* mergeKLists(vector<ListNode*>& lists) {
19         priority_queue<ListNode* ,vector<ListNode*> , cmp> que;
20for(auto head:lists){
21if(head)   que.push(head);
22        }
2324         ListNode* ans = new ListNode(0);
25         ListNode* res = ans;
2627while(!que.empty()){
28             ListNode* p = que.top();
29            que.pop();
30if(p->next){
31                 que.push(p->next);
32            }
33             res->next = p;
34             res = res->next;
35        }
36return ans->next;
37    }
38 };

 

原文：https://www.cnblogs.com/Asumi/p/12513914.html

内容总结

以上是互联网集市为您收集整理的【Leetcode】合并K个排序链表全部内容，希望文章能够帮你解决【Leetcode】合并K个排序链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1229041.html

来源：【匿名】