23. 合并K个升序链表

• • 食用指南：
  • 题目描述：
  • 题目分析：
  • 算法模板:
  • 代码实现：
  • • 法一：漏斗堆
    • 法1.5：迭代器 / 范围for不需要判断输入为空
    • 法二：两两合并链表
  • 注意点：
  • • 1. 自定义STL中的堆：
    • 2. 被空值卡输入：

食用指南：

Leetcode专栏开启了，由于博主闭关期末，所以每日只能一题
尽量做到一题多解，先说思路，之后代码实现，会添加必要注释
语法或STL内容会在注意点中点出，新手友好
欢迎关注博主神机百炼专栏，内涵算法基础详细讲解和代码模板

题目描述：

• 给你一个链表数组，每个链表都已经按升序排列，

  请你将所有链表合并到一个升序链表中，返回合并后的链表。

• 代码背景

class Solution {
public:ListNode* mergeKLists(vector& lists) {}
};

• 题目来源：https://leetcode.cn/problems/merge-k-sorted-lists/

题目分析：

• 法一：漏斗堆

  建立一个大小为k的堆，开始将各个链表头节点加入堆中

  每次将堆中值最小的节点加入最终的主链表中，同时将该节点的下一个节点入堆

  堆内每次push() pop()的时间复杂度都是O(log(k))

  共n个节点，每个节点先push()入堆，最终pop()出堆，总时间复杂度为O(2·n·log(k))
  

• 法二：两两合并链表

  每次遍历两条链表，将其合并，返回头节点作为最终主链表的头节点，

  一共两两合并k-1次，每次主链表长度逐步增加，每次两两合并耗时是上一次加上一条链表长度
  假设每条链表最长n个节点，总时间复杂度为(n + 2n + …… + kn) = O(k²·n)

算法模板:

• 静态堆

代码实现：

法一：漏斗堆

class Solution {
public:struct cmp{bool operator()(ListNode* p, ListNode* q){return p->val > q->val;                 //升序链表，小根堆，用>号}};ListNode* mergeKLists(vector& lists) {if(lists.size() == 0) return nullptr;ListNode* dummy = new ListNode();ListNode* p = dummy;priority_queue, cmp> heap;for(int i=0; iif(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& lists) {ListNode* dummy = new ListNode();ListNode* p = dummy;priority_queue, 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& lists) {ListNode* head = nullptr;for(int i=0; iif(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, cmp1> heap1;
priority_queue, cmp2> heap2;

2. 被空值卡输入：

• 输入空值情况1：vector<>中没有元素
• 对策：上手先判空

//输入：[]
class Solution {
public:ListNode* mergeKLists(vector& lists) {if(lists.size() == 0) return nullptr;}
};

• 输入空值情况2：vector<>中含有空元素
• 对策：向堆中插入元素前先审查元素是不是nullptr

//输入：[[]]
class Solution {
public:ListNode* mergeKLists(vector& lists) {if(lists.size() == 0) return nullptr;priority_queue, cmp> heap;for(int i=0; iif(lists[i])heap.push(lists[i]);}}
};