给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
解题思路一：优先级队列
这道题的暴力破解简单说一下，因为有 k 个链表，假设所有链表的平均长度为 n，那么合并这 k 个升序链表，其实就是先拿两个链表去合并，合并成一个新的链表，就拿这个链表去和第三个链表合并变成一个新的链表，以此类推……
这样子一来时间复杂度是非常高的，达到了 O(n * k^2) 级别，所以我们必须要优化一下才能跑过这道困难题！
我们仔细一想，其实之所以时间复杂度这么高，其实是因为我们得两两去合并最后得到一个链表，那么其实我们可以先创建一个新的头节点 newhead，然后一次性比较多个链表进行合并呀，假设有三个链表的话，如下图所示：
此时问题就来了，在多个链表中，我们需要快速找到哪个节点是最小的，不然的话每次都需要遍历 k 次去找到最小的那个，时间复杂度其实没有明显的提高，所以就引入了优先级队列，也就是堆，并且是一个小根堆，因为我们要找的最小的那个！
引入了小根堆之后问题就很好的解决了，剩下的就是处理完所有的节点！
首先让 k 个链表的头节点先插入到小根堆中，此时堆顶就是最小的那个节点 top，将其插入到 newhead 链表中，然后将其从小根堆中 pop 掉，然后将 top->next 插入到小根堆中，直到堆中元素为空为止！
注意关键操作就是判断 top->next 是否为空，为空的话就不需要再插入了，最后遍历到所有链表节点结束之后，剩下的就是堆中的元素，最后堆中节点也 pop 完就代表都插入到了 newhead 中了！
因为一共是 k 个链表，假设每个链表平均节点是 n 个，又因为插入堆的操作是 logk，所以最后的时间复杂度就是 O(n * k * logk)。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
struct cmp
{
bool operator()(const ListNode* node1, ListNode* node2)
{
return node1->val > node2->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 1. 创建一个小根堆（因为是自定义类型，所以需要我们自己写一个比较器）
priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
// 2. 然后将每个链表的头节点插进去
for(int i = 0; i < lists.size(); ++i)
{
if(lists[i] != nullptr) // 注意需要判空
heap.push(lists[i]);
}
// 3. 每次从堆顶弹出最小的节点插入到新的头节点后面，然后插入新节点，直到堆为空为止
ListNode* newhead = new ListNode();
ListNode* cur = newhead;
while(!heap.empty())
{
ListNode* top = heap.top();
heap.pop();
cur->next = top;
cur = cur->next;
if(top->next != nullptr)
heap.push(top->next);
}
cur = newhead->next;
delete newhead;
return cur;
}
};解题思路二：分治归并思想
如果面试官还要求说需要递归解决问题，那么可以考虑分治归并的思想，因为这些链表由数组 lists 管理，我们可以先将其进行分治，递归到两两进行合并，然后返回给上一层，以此类推，如下图所示：
因为一共有 k 个链表，所以递归的层次一共是 logk 层，假设每个链表平均节点是 n 个，最后的时间复杂度就是 O(n * k * logk)，和上面的优先级队列解法其实是一样d
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
ListNode* merge(vector<ListNode*>& lists, int left, int right)
{
if(left > right) return nullptr;
if(left == right) return lists[left]; // 一个链表的情况
// 先进行分治
int mid = (left + right) >> 1;
ListNode* left_list = merge(lists, left, mid);
ListNode* right_list = merge(lists, mid + 1, right);
// 合并左右两个链表
ListNode* newhead = new ListNode();
ListNode* cur = newhead;
while(left_list != nullptr && right_list != nullptr)
{
if(left_list->val <= right_list->val)
{
cur->next = left_list;
left_list = left_list->next;
}
else
{
cur->next = right_list;
right_list = right_list->next;
}
cur = cur->next;
}
if(left_list != nullptr)
cur->next = left_list;
if(right_list != nullptr)
cur->next = right_list;
cur = newhead->next;
delete newhead;
return cur;
}
};