这个题目是一个很经典的链表题目，可以有几种解题方法，对这个题理解透了也可以加深对链表的理解，另外也可以复习一下分治以及堆。因此这里做个笔记，个人在理论理解方面还有待提高，因此记录的难免有些小毛病。

题目：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
给你一个链表数组，每个链表都已经按升序排列。

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

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]
示例 3：输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

题解：

先假设设有k个链表，每个链表的平均长度为n，方便后面复杂度分析。

思路1：首先想到的最简单的方法就是按顺序进行合并，那么这个题目就仅仅是 合并两个有序链表 的复杂化。我们先让第一个链表和第二个链表合并，合并得到的结果再和第三个链表合并，以此类推。

• 时间复杂度：O(n+2n+…+kn)=O(k²n)
• 空间复杂度：O(1)

C++代码1：
提交居然没有超时！！！

class Solution {//合并两个链表ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* head = new ListNode(0);ListNode* node = head;while(l1!=nullptr && l2!=nullptr){if(l1->val < l2->val){node->next = l1;l1 = l1->next;node = node->next;}else{node->next = l2;l2 = l2->next;node = node->next;}}if(l1 == nullptr){node->next = l2;}else{node->next = l1;}return head->next;}
public://合并k个链表ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* l1 = nullptr;//这里为了防止链表数组只有一个链表，直接用list[0]和list[1]合并会越界//所以不妨让第一个链表为空，反正合并链表的程序能处理这种情况ListNode* l2;for(int i = 0; i < lists.size(); ++i){l2 = lists[i];l1 = mergeTwoLists(l1,l2);//合并结果赋值给l1}return l1;}
};

思路2：两两合并，即每轮合并先两两合并，之后对合并的结果再进行两两合并，就像天下第一武道会，先两个人对战，胜者参加下一轮比赛。不过这里不是对战，而是合并后再参加下一轮合并，当然，这里合并可能有轮空，直接参加后面的合并。这里其实用到一个分治的思想，k个链表合并化成多轮两两合并。

注：归并排序算法很好地应用了分治思想，如果对分治思想的编码逻辑有些遗忘，就可以回顾一下归并排序的代码，简单又好懂。要小试身手，可以看 数组中的逆序对。

• 时间复杂度：对于k个链表要进行⌈logk⌉轮合并，每轮合最多进行kn次比较，因此时间复杂度为O(knlogk)
  当然也可以这么算：$O(\frac{k}{2}×2n ＋ \frac{k}{4}×4n +...+\frac{k}{k}×kn)=O(knlogk)$
• 空间复杂度：如果用递归方法要用栈空间，一共要进行 logk 轮比较，所以 O(logk)

C++代码2：
与思路1的代码相比无非是加入了一个merge函数，用来分治。

class Solution {//合并两个链表ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* head = new ListNode(0);ListNode* node = head;while(l1!=nullptr && l2!=nullptr){if(l1->val < l2->val){node->next = l1;l1 = l1->next;node = node->next;}else{node->next = l2;l2 = l2->next;node = node->next;}}if(l1 == nullptr){node->next = l2;}else{node->next = l1;}return head->next;}//这里用到一个分治的思想ListNode* merge(vector<ListNode*> &lists, int l, int r) {if (l == r) return lists[l];if (l > r) return nullptr;int mid = (l+r)/2;ListNode* left = merge(lists,l,mid);ListNode* right = merge(lists,mid+1,r);return mergeTwoLists(left,right);}
public://合并k个链表ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* res = merge(lists,0,lists.size()-1);return res;}
};

思路3：题目的复杂性主要在于比较排序的过程，因此我们可以使用最小堆进行辅助，这样子就能方便得到的一个有序序列。至于怎么实现最小堆，直接用C++标准库的priority_queue就可以了，不过要自己定义一个比较规则。具体合并思路为，我们先遍历链表，把链表节点push进堆，之后再top，pop。注意这里我们可以利用好“K个升序链表”这一信息，这一信息告诉我们最小值都在这些链表的首节点中，因此可以先把每个链表的首个节点push进堆，之后再弹出某个链表首节点时再将后面的节点push进堆，这样一来堆中元素数量就不会超过k个。

• 时间复杂度：由于往大小为k的堆插入数据的时间复杂度为 O(logk)，因此该方法是时间复杂度是 O(knlogk)
• 空间复杂度：由于要维护一个大小为 k 的堆，因此空间复杂度是O(k)。

C++代码3：
注意如何自定义priority_queue的优先级规则。

struct cmp{bool operator()(ListNode* a,ListNode* b){return a->val >= b->val;}
};
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*,vector<ListNode*>,cmp> pq;for(auto node:lists){if(node)//防止空链表[[]]输入pq.push(node);}ListNode* head = new ListNode(0);ListNode* cur = head;while(!pq.empty()){ListNode* tmp = pq.top();cur ->next = tmp;cur = cur->next;pq.pop();if(tmp->next){pq.push(tmp->next);}}return head->next;}
};