[算法]——链表（二）
目录
一、前言
二、正文
1.合并K个升序链表
1.1 题目解析
1.2 算法原理
1.3 具体代码
三、结语
一、前言
本文将继续为大家带来链表相关的学习，希望小伙伴能够从中有所收获！！！
二、正文
1.合并K个升序链表
1. 合并 K 个升序链表 - 【力扣】
1.1 题目解析
本题要求我们能够将题目中所给的K个升序链表进行合并，合并后为一个依旧为升序的链表
1.2 算法原理
对于本题，笔者会为大家讲解三种解法。
①暴力解法（时间复杂度:Nk²）：
相信暴力解法是很多小伙伴立马就能想到的解法，因为力扣上有一道与本题类似的题目，就是合并两个有序链表，既然两个我们都可以合并，k个的不是可以先合并第一个和第二个，然后再和第三个合并，第四个……直至第k个，但是由于这样子的话，我们假设一个链表长度为N，对于第一个链表，它需要和k-1个链表合并；第二个链表需要和k-2个链表合并，因此最后的时间复杂度就是O（Nk²）,当k趋近于N时，时间复杂度是N³，很有可能会超时，因此就不将代码列出了，感兴趣的小伙伴可以自己书写尝试一下
②优先队列法（时间复杂度:Nk*logk）
优先队列法可以看做是对暴力解法的优化，因为在暴力解法中我们发现有时候一个元素往往会被比较多次，因此就使得时间复杂度变高。但是如果我们采取优先级队列，即堆排序的方式，建立一个大小为k小根堆，将每个链表的首个元素插入，堆顶的元素就是最小的元素，不断插入，拿出节点，通过这样的方式我们就能将k个有序的链表合并了。由于堆排序的时间复杂度为logk，插入所有元素是Nk，因此总的时间复杂度为O(Nk*logk)
③分治-归并法（时间复杂度:Nk*logk）
其实本题还可以采取分治-归并的方法，与我们之前讲过的归并排序思路相同，想要合并k个升序链表，我们可以先将k个链表分为左右两部分，先将左边部分链表合并成一个升序链表，再将右边部分链表合并成一个升序链表，最后再将左右合并后的两个链表合并成一个升序链表。而左右部分合并的过程同上，最后合并k个升序链表就不断分治成只需合并两个链表这样简单地操作。时间复杂度的话，由于合并链表需要nk，一共合并logk次，因此总的时间复杂度为O（nk*logk），与优先级队列的时间复杂度相同
1.3 具体代码
//合并k个升序链表
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 Solution1 {
public:
//优先级队列
struct cmp
{
bool operator()(const ListNode* l1, const ListNode* l2)
{
return l1->val > l2->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 创建一个小根堆
priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
//让所有的头结点进入小根堆
for (auto l : lists)
if (l) heap.push(l);
// 合并k个有序链表
ListNode* ret = new ListNode;
ListNode* prev = ret;
while (!heap.empty())
{
ListNode* t = heap.top();
heap.pop();
prev->next = t;
prev = t;
if (t->next) heap.push(t->next);
}
prev = ret->next;
delete ret;
return prev;
}
};
class Solution2 {
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];
//1.平分数组
int mid = (left + right) >> 1;
//[left,mid] [mid+1, right]
//2. 递归处理左右区间
ListNode* l1 = merge(lists, left, mid);
ListNode* l2 = merge(lists, mid + 1, right);
//3. 合并两个有序链表
return mergeTwoList(l1, l2);
}
ListNode* mergeTwoList(ListNode* l1, ListNode* l2)
{
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
//合并两个有序链表
ListNode head;
ListNode* cur1 = l1, * cur2 = l2, * prev = &head;
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;
}
return head.next;
}
};三、结语
到此为止，本文关于链表（二）内容到此结束了，如有不足之处，欢迎小伙伴们指出呀！
关注我 _麦麦_分享更多干货：_麦麦_-CSDN博客
大家的「关注❤️ + 点赞👍 + 收藏⭐」就是我创作的最大动力！谢谢大家的支持，我们下期见！
欢迎大家参观我的算法专栏：麦麦的算法专栏
https://blog.csdn.net/m0_73953114/category_12866812.html