合并K个排序链表
- 难度： 困难
- 通过率： 31.9%
- 题目链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
题目描述
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
解法：
使用一个优先队列来存储链表的头结点，这样就可以很方便地取到值最小的节点了。取出值最小的节点后，如果它的下一个节点不为空，再加入到优先队列中。当优先队列为空时，就合并完成了。
class Solution {
public:
ListNode *mergeKLists(vector<ListNode*>& lists) {
if(lists.empty()) return nullptr;
auto cmp = [](ListNode *a, ListNode *b) {
return a->val > b->val;
};
priority_queue<ListNode *, vector<ListNode *>, decltype(cmp)> pq(cmp);
for_each(lists.begin(), lists.end(), [&pq](ListNode *node) {
if(node){
pq.push(node);
}
});
ListNode dummy(0);
ListNode *p = &dummy;
while (!pq.empty()) {
ListNode *node = pq.top();
pq.pop();
p->next = node;
p = p->next;
node = node->next;
if (node) {
pq.push(node);
}
}
return dummy.next;
}
};