1、题目描述
- Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
2、问题关键：建立一个小根堆，放入三个的头结点，取出最小的那个，就把最小的那个的下一个放入堆里，重复操作。
- 优先队列默认建立的是大根堆，可以对元素取反就相当于小根堆。
- 放入结点的值和指针，-list->val和list。
- 建立一个虚拟头指针，避免不必要的边界条件
- 最后将cur指向空，cur->next = nullptr；
3、C++代码：
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<pair<int, ListNode*>> heap;//默认大根堆。
for (auto list : lists){
if (list) heap.push({-list->val, list});//将每个链表的头加入堆中。
}
ListNode *dummy = new ListNode(-1);//建立虚拟头结点。
auto cur = dummy;
while(heap.size()){
auto t = heap.top();
heap.pop();
if (t.second->next) heap.push({-t.second->next->val, t.second->next});//取出最小值，并将其下一个压入堆中。
cur->next = t.second;
cur = cur->next;
}
cur->next = nullptr;//将最后一个指向空。
return dummy->next;
}
};
