leetcode C++ 23. 合并K个排序链表 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

一、思路：

      第一种：求出每一个链表的最小值，然后把这个节点放到合并的结果链表里面，这个链表指向next

      第二种：优先级队列，头结点放到优先级队列里面，将top的那一个放到合并的链表里面，再讲top指向next,push到队列里面

二、代码

     第一种思路：

class Solution { public:ListNode *insert(ListNode *nowNode, int val) {if (nowNode == NULL)return new ListNode(val);else {nowNode->next = new ListNode(val);return nowNode->next;}}ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode *res = NULL, *nowNode = res;while (true) {bool isAllNull = true;int minVal = INT_MAX, pos = -1;for (int i = 0; i < lists.size(); i++){if (lists[i] != NULL) {isAllNull = false;if (lists[i]->val < minVal) {pos = i;minVal = lists[i]->val;}}}if (isAllNull)return res;lists[pos] = lists[pos]->next;if (nowNode == NULL)res = nowNode = insert(nowNode, minVal);elsenowNode = insert(nowNode, minVal);}return res;} };

 

     第二种思路：来源：https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/c-you-xian-dui-lie-liang-liang-he-bing-fen-zhi-he-/

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> pri_queue;// 建立大小为k的小根堆for(auto elem : lists){if(elem) pri_queue.push(elem);}// 可以使用哑节点/哨兵节点ListNode dummy(-1);ListNode* p = &dummy;// 开始出队while(!pri_queue.empty()){ListNode* top = pri_queue.top(); pri_queue.pop();p->next = top; p = top;if(top->next) pri_queue.push(top->next);}return dummy.next; } };

 

总结

以上是生活随笔为你收集整理的leetcode C++ 23. 合并K个排序链表 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。