链表OJ（十二）23.合并K个升序链表困难优先级队列中存放指针结点

 

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

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

示例 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 == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4

 对于仿函数的复习 priority_queue 接口使用（仿函数、函数指针解决优先级队列存放自定义类型元素、指针类型元素）_priority queue接口-CSDN博客

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 Com { public: bool operator()(ListNode* left, ListNode* right) { return left->val > right->val; 出错点1 大于小于关系判断 } }; class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*, vector<ListNode*>, Com> q; for (auto& e : lists) if (e) 出错点2 没有对访问的节点进行判空处理 q.push(e); ListNode* newhead = new ListNode(-1); newhead->next = nullptr; ListNode* pre = newhead; while (!q.empty()) { ListNode* cur = q.top(); q.pop(); pre->next = cur; pre = pre->next; cur = cur->next; if (cur) q.push(cur); } return newhead->next; } }; int main() { Solution s; ListNode* l1 = new ListNode(0); ListNode* l2 = new ListNode(2); ListNode* l3 = new ListNode(3); ListNode* l4 = new ListNode(4); ListNode* l5 = new ListNode(5); l1->next = l2; l2->next = l3; l3->next = l4; l4->next = l5; ListNode* p1 = new ListNode(1); ListNode* p2 = new ListNode(3); ListNode* p3 = new ListNode(6); ListNode* p4 = new ListNode(9); p1->next = p2; p2->next = p3; p3->next = p4; ListNode* z1 = new ListNode(2); ListNode* z2 = new ListNode(3); ListNode* z3 = new ListNode(6); z1->next = z2; z2->next = z3; vector<ListNode*> v = { l1, p1, z1 }; s.mergeKLists(v); return 0; }