链表" />
23. 合并K个升序链表
食用指南：
Leetcode专栏开启了，由于博主闭关期末，所以每日只能一题
尽量做到一题多解，先说思路，之后代码实现，会添加必要注释
语法或STL内容会在注意点中点出，新手友好
欢迎关注博主神机百炼专栏，内涵算法基础详细讲解和代码模板
题目描述：
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
}
};
- 题目来源：https://leetcode.cn/problems/merge-k-sorted-lists/
题目分析：
-
法一：漏斗堆
每次将堆中值最小的节点加入最终的主链表中，同时将该节点的下一个节点入堆
堆内每次push() pop()的时间复杂度都是O(log(k))
-
法二：两两合并链表
每次遍历两条链表，将其合并，返回头节点作为最终主链表的头节点，
一共两两合并k-1次，每次主链表长度逐步增加，每次两两合并耗时是上一次加上一条链表长度
假设每条链表最长n个节点，总时间复杂度为(n + 2n + …… + kn) = O(k2·n)
堆" />算法模板:
- 静态堆
代码实现：
法一：漏斗堆
class Solution {
public:
struct cmp{
bool operator()(ListNode* p, ListNode* q){
return p->val > q->val; //升序链表，小根堆，用>号
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return nullptr;
ListNode* dummy = new ListNode();
ListNode* p = dummy;
priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
for(int i=0; i<lists.size(); i++){
if(lists[i])
heap.push(lists[i]);
}
while(!heap.empty()){
ListNode* tmp = heap.top();
p->next = tmp;
p = p->next;
heap.pop();
if(tmp->next)
heap.push(tmp->next);
}
p->next = nullptr;
return dummy->next;
}
};
法1.5：迭代器 / 范围for不需要判断输入为空
class Solution {
public:
struct cmp{
bool operator()(ListNode* p, ListNode* q){
return p->val > q->val; //升序链表，小根堆，用>号
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* dummy = new ListNode();
ListNode* p = dummy;
priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
for(auto q : lists){
if(q) heap.push(q);
}
while(!heap.empty()){
ListNode* tmp = heap.top();
heap.pop();
p = p->next = tmp;
if(tmp->next)
heap.push(tmp->next);
}
p->next = nullptr;
return dummy->next;
}
};
法二：两两合并链表
class Solution {
public:
ListNode* mergeTwoLists(ListNode* p, ListNode* q){
ListNode* dummy = new ListNode();
ListNode* i = p, *j = q, *k = dummy;
while(i && j){
if(i->val < j->val) {
k = k->next = i;
i = i->next;
}else{
k = k->next = j;
j = j->next;
}
}
while(i){
k = k->next = i;
i = i->next;
}
while(j){
k = k->next = j;
j = j->next;
}
k->next = nullptr;
return dummy->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* head = nullptr;
for(int i=0; i<lists.size(); i++){
if(lists[i]){
head = mergeTwoLists(head, lists[i]);
}
}
return head;
}
};
注意点：
1. 自定义STL中的堆：
- 大根堆：
priority_queue<元素类型> A; //默认大根堆
priority_queue<元素类型, vector<元素类型>, less<元素类型>>B; //大根堆
- 小根堆：
priority_queue<元素类型, vector<元素类型>, greater<元素类型> > C; //小根堆
-
仿函数类自定义比较函数：
由于指针直接比较大小，其实是比较地址高低，所以自定义比较函数尤其对于指针适用
struct cmp1{
bool operator()(ListNode* p, ListNode* q){
return p->val > q->val; //大于为小根堆
//return p->val < q->val; //小于为大根堆
}
};
//如果ListNode类本身重载过< >运算符号，则直接解引用即可
struct cmp2{
bool operator()(ListNode* p, ListNode* q){
return *p > *q; //大于为小根堆
//return *p < *q; //小于为大根堆
}
};
priority_queue<ListNode*, vector<ListNode*>, cmp1> heap1;
priority_queue<ListNode*, vector<ListNode*>, cmp2> heap2;
2. 被空值卡输入：
- 输入空值情况1：vector<>中没有元素
- 对策：上手先判空
//输入：[]
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return nullptr;
}
};
- 输入空值情况2：vector<>中含有空元素
- 对策：向堆中插入元素前先审查元素是不是nullptr
//输入：[[]]
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return nullptr;
priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
for(int i=0; i<lists.size(); i++){
if(lists[i])
heap.push(lists[i]);
}
}
};
