LeetCode 23. 合并K个排序链表
原题链接
困难
作者:
ShineShaye
,
2022-07-05 11:00:32
,
所有人可见
,
阅读 121
帮你标明了 所有 可能踩的坑!
/**
题目:合并k个有序链表
思路:
每次要找k个有序表头的最小值
建立一个小根堆是最快的(存储的是k个链表当前的首个结点)
对于自定义的数据结构(ListNode),建立大根堆时需要传入排序方式(仿函数,重载调用运算符)
实现对于结点按照p->val来排序,并且是小根堆
* 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:
class cmp{
// class默认属性为private,写仿函数一定要加public,或者使用struct
public:
bool operator()(ListNode* a, ListNode* b)
{
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode* >, cmp> pri;
// 建立一个冗余结点,存储合并后的链表
auto dummy = new ListNode(-1);
// 向堆中存入所有链表的当前头结点
for(auto l : lists)
// 这里一定要判空结点,因为如果某个链表为空,头结点l是nullptr类型,没有val这个成员,插入堆时找不到比较方法
if(l) pri.push(l);
// 每次取出堆头,加入到合并后的链表,如果该结点有后续结点,要放入堆中
auto tail = dummy;
while(!pri.empty())
{
auto tmp = pri.top();
pri.pop();
tail = tail->next = tmp; // 尾结点一定要记得后移,否则会反复覆盖头部
if(tmp->next) pri.push(tmp->next);
}
return dummy->next;
}
};