lc23 k路归并
可以采用和二路归并相同的思路,选取每一轮的最小值。
如何选取最小值? =》 用小根堆保存每一组的最小值(保存指针)
//改成小根堆
struct Cmp {
bool operator() (ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*,vector<ListNode*>,Cmp> heap;
auto dummy = new ListNode(-1),cur = dummy;
for(int i = 0;i < lists.size();i ++)
if(lists[i]) heap.push(lists[i]);
while(heap.size()) {
auto t = heap.top();
heap.pop();
cur -> next = t;
cur = cur -> next;
if(t -> next) heap.push(t -> next);
}
return dummy -> next;
}