leetcode-23-链表题-合并K个排序链表

题目

1.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
// 同时比较所有链表的首节点,利用优先级队列,每次弹出最小值
class Solution {
public:
// 定义比较操作
struct cmp{
bool operator()(ListNode *a, ListNode *b){
return a->val > b->val;
}
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.empty()) return NULL;

// 使用优先级队列,每次弹出最小值
priority_queue<ListNode* ,vector<ListNode*> , cmp> heapk;
for(auto list : lists){
if(list) heapk.push(list);
}

ListNode *res = new ListNode(-1);
ListNode *tempRes = res;
while(!heapk.empty()){
ListNode *top = heapk.top();
heapk.pop();
tempRes->next = top;
tempRes = tempRes->next;
if(top->next) heapk.push(top->next);
}

tempRes = res->next;
delete res;
return tempRes;
}
};