三种方法:
优先级队列(最小堆)
/**
* 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:
struct Cmp{
bool operator()(ListNode*a,ListNode*b){
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0)
return NULL;
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
//利用二叉堆的性质 最小堆 优先级队列
//堆构造好之后就可以直接使用了
priority_queue <ListNode*,vector<ListNode*>,Cmp> heap;
//默认是最大堆 自己修改最小堆
//第一个参数:堆中节点数据类型
//第二个参数 堆使用的数据结构
//第三个参数 bool值一般指比较大小 返回大于说明大的值往队列后面扔
//构造最小堆 传入元素
for(ListNode*x:lists)
{
while(x)
{
heap.push(x);
x = x->next;
}
}
while(!heap.empty())
{
int y = heap.top()->val;
heap.pop();
p->next = new ListNode(y);
p = p->next;
}
return dummy->next;
}
};
两两比较
分治
参考:
https://www.cnblogs.com/lailailai/p/3759825.html
leetcode