个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创链表(4)_合并K个升序链表_面试题
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
1. 题目链接
OJ链接 : 合并K个升序链表
2. 题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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
3. 解法
方法一: 暴力解法
算法思路:
暴力算法很容易想到, 我们可以联想合并两个有序链表那道题, 那么有这道题的启发, 我们可以直接两两合并这K个升序链表.至于时间复杂度的分析, 我放到了代码展示的模块中, 说实话, 在面试中, 尽量不要写出暴力的方法, 一般通不过的~~
代码展示:
/**
* 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) {
if(lists.empty()) return nullptr;
ListNode* cur1 = lists[0];
ListNode* head = new ListNode(0);
for(int i = 1; i < lists.size(); i++)
{
ListNode* cur2 = lists[i];
ListNode* prev = head;
while(cur1 || cur2)
{
if(cur1 && cur2)
{
if(cur1->val < cur2->val)
{
prev->next = cur1;
prev = cur1;
cur1 = cur1->next;
}
else
{
prev->next = cur2;
prev = cur2;
cur2 = cur2->next;
}
}
else
{
if(cur1)
{
prev->next = cur1;
prev = cur1;
cur1 = cur1->next;
}
if(cur2)
{
prev->next = cur2;
prev = cur2;
cur2 = cur2->next;
}
}
}
cur1 = head->next;
head->next = nullptr;
}
delete head;
return cur1;
}
};
怎么说呢, 纯暴力, 没有技巧, 但是我万万没想到啊~, 居然过了~
但是, 这种题大概率会在面试题中遇到, 如果你给hr写出这样的代码, hr大概率会让你想想其他的方法(递归...), 反正就是要比暴力算法要好, 想不到的话, 可能直接让你回去等通知了(寄了)
那这个暴力算法真的有这么不堪吗? 别着急, 接下来我就详细分析一下它的时间复杂度.
暴力算法时间复杂度分析:
合并两个链表的时间复杂度为 O(N)，其中 N 是两个链表的总节点数。由于每次合并可能会处理 M 个节点。外层循环运行 K - 1 次（因为合并 K 个链表需要进行 K - 1 次合并），内层合并两个链表的操作总体上处理 M 个节点。因此，时间复杂度为：
O(M⋅K)其中 M 是所有链表节点的总数。
又因为我们的链表在合并的过程中是递增的, 假如每个链表长度固定为n, 那我们每合并一次, 我们的链表长度就会增加n, 也就是说我们合并时链表增长为: n, 2n, 3n, 4n, ... kn , 所以我们总的时间复杂度为: (n + kn)(k - 1)/2
总的时间复杂度为: O(k^2*n)
假如说n ~= k 的话, 那我们暴力算法的时间复杂度为O(n ^ 3) , 非常恐怖, 这道题我们能够通过的原因在于n < 10^2
方法二: 利用优先级队列做优化
算法原理:
合并两个有序链表是比较简单的, 就是使用双指针一次比较链表1, 链表2未排序的最小元素, 选择更小的哪一个加入有序的答案链表中.
合并k个链表时, 我们依旧可以选择k个链表中, 头节点值最小的哪一个, 那么如何快速的得到头节点最小的是哪一个呢? 用堆这个数据结构就好了~
我们可以把所有的头节点放进一个小根堆中, 这样就能快速找到每次k个链表中, 最小的元素是那个.
代码展示:
/**
* 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 {
struct cmp{
bool operator()(const ListNode* l1, const ListNode* l2)
{
return l1->val > l2->val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
for(auto l : lists)
if(l) heap.push(l);
ListNode* head = new ListNode(0);
ListNode* prev = head;
while(!heap.empty())
{
ListNode* t = heap.top();
heap.pop();
prev->next = t;
prev = t;
if(t->next) heap.push(t->next);
}
prev = head->next;
delete head;
return prev;
}
};
时间复杂度分析
空间复杂度：O(K)，用于存储 K 个链表的头节点在堆中。
时间复杂度：
将 K 个头节点插入堆：O(K* log K)。
每个节点的处理（假设总共 N 个节点）：O(N* log K)，因为每次取出最小值和插入下一个节点都涉及到堆的操作。
因此，整体时间复杂度为 O(N log K)，其中 N 是所有链表中节点的总数，K 是链表的数量。
假设每个链表的节点为n, 所有链表的节点总数为: kn, 即总的时间复杂度为 : O(n * k * logk)
方法三: 分治 - 递归
算法原理:
逐一比较时，答案链表越来越长，每个跟它合并的小链表的元素都需要比较很多次才可以成功排序。
比如，我们有 8 个链表，每个链表长为 100。
逐一合并时，我们合并链表的长度分别为(0, 100), (100, 100), (200, 100), (300, 100), (400, 100), (500, 100), (600, 100), (700, 100)。所有链表的总长度共计 3600。
如果尽可能让长度相同的链表进行两两合并呢？这时合并链表的长度分别是(100, 100) x 4, (200, 200) x 2, (400, 400)，共计 2400。比上⼀种的计算量整整少了 1 / 3。
迭代的做法代码细节会稍多一些, 这里还是推荐方法二, 不过还是怕面试中, 会被问到~~
算法流程:
1. 特判，如果题目给出空链表，无需合并，直接返回；
2. 返回递归结果。
递归函数设计：
1. 递归出口：如果当前要合并的链表编号范围左右值相等，无需合并，直接返回当前链表；
2. 应用二分思想，等额划分左右两段需要合并的链表，使这两段合并后的长度尽可能相等；
3. 对左右两段分别递归，合并[l, r]范围内的链表；
4. 再调用 mergeTwoLists 函数进行合并（就是合并两个有序链表）
代码展示:
/**
* 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* l1 = merge(lists, left, mid);
ListNode* l2 = merge(lists, mid + 1, right);
return mergecombine(l1, l2);
}
ListNode* mergecombine(ListNode* l1, ListNode* l2)
{
if(l1 == nullptr) return l2;
if(l2 == nullptr) return l1;
ListNode* head = new ListNode(0);
ListNode* prev = head, *cur1 = l1, *cur2 = l2;
while(cur1 && cur2)
{
if(cur1->val < cur2->val)
{
prev = prev->next = cur1;
cur1 = cur1->next;
}
else
{
prev = prev->next = cur2;
cur2 = cur2->next;
}
}
if(cur1) prev->next = cur1;
if(cur2) prev->next = cur2;
prev = head->next;
delete head;
return prev;
}
};
时间复杂度分析
分治递归的时间复杂度：每次递归都将链表数组分成两半，所以递归的深度为 O(log K)，其中 K 是链表的数量。
在每一层的递归中，需要合并 K 个链表中的部分，最多需要遍历每个链表的所有节点。假设所有链表的节点数总和为 N，则合并的时间复杂度为 O(N)。
因此，总体时间复杂度为 O(N log K)，其中 N 是所有链表中的节点数，K 是链表的数量。假设每个链表的节点为n, 所有链表的节点总数为: kn, 即总的时间复杂度为 : O(n * k * logk)
空间复杂度：由于递归栈的深度为 O(log K)，所以空间复杂度是 O(log K)，这是递归分治的开销。
合并过程中的额外空间是常数级别的，因此整体空间复杂度为 O(log K)。