LeetCode-23:合并K个排序链表
一、题目描述
二、解题思路
- 我们可以采用遍历 v e c t o r vector vector元素的方法,对其进行插入排序,但是这样控制成本比较高
- 因此想到用小根堆的方法,,遍历 v e c t o r vector vector元素的同时将元素插入到小根堆里,进行堆排序
- 每次元素从小根堆弹出时,即为当前最小值,进行插入到链表尾的操作即可
三、完整代码
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto q = new priority_queue<int, vector<int>, greater<int> >; //小根堆声明方法,默认为大根堆
int len = lists.size();
for(int i = 0; i < len; i++){
auto p = lists[i];
while(p){
q->push(p->val);
p = p->next;
}
}
auto dummyHead = new ListNode(-1);
auto p = dummyHead;
while(!q->empty()){
auto ins = new ListNode(q->top());
q->pop();
p->next = ins;
p = p->next;
}
p = dummyHead->next;
delete dummyHead;
dummyHead = nullptr;
delete q;
q = nullptr;
return p;
}
};
四、运行结果
三个月前是插入排序,虽然节省了空间,但是速度很慢,现在改为堆排序,能快一点