牛客热题：合并K个升序链表

本文主要是介绍牛客热题：合并K个升序链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

牛客热题：合并K个升序链表

题目链接：

合并k个已排序的链表_牛客题霸_牛客网 (nowcoder.com)

方法一：复用2个升序链表的方法

思路：

• 首先我们知道如何合并两个升序链表
• 那么我们先将k个的前两个合并，然后再将和这个合并的链表和下一个链表合并…直到所有的链表都被合并

代码：

 ListNode* Merge(ListNode* pHead1, ListNode* pHead2){//申请一个哨兵位ListNode* head = new ListNode(0);ListNode* cur = head;while(pHead1 != nullptr && pHead2 != nullptr){if(pHead1->val <= pHead2->val){cur->next = pHead1;cur = cur->next;pHead1 = pHead1->next;}else{cur->next = pHead2;cur = cur->next;pHead2 = pHead2->next;}}//p1未完的情况while(pHead1 != nullptr){cur->next = pHead1;cur = cur->next;pHead1 = pHead1->next;}//p2未完的情况while(pHead2 != nullptr){cur->next = pHead2;cur = cur->next;pHead2 = pHead2->next;}return head->next;}ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.size() == 0) return nullptr;ListNode* ret = lists[0];for(int i = 1; i < lists.size(); ++i){ret = Merge(ret, lists[i]);}  return ret;}

复杂度：

时间复杂度:O($N^2$), 但其实一般达不到O($N^2$);

• 对于第一个链表:我们遍历了k-1次
• 对于第二个链表:我们遍历了k-2次
• …
• 对于最后一个链表:我们遍历了1次

由于所有的链表的长度加起来为$n$，那么平均长度为$n/k$,

每个链表最多被遍历k - 1次，我们放缩为k次，那么需要最多$n\ast n$次运算.

空间复杂度：O(1), 使用了常数个额外的空间。

方法二：第一种方法的分治优化–>借鉴牛客题解

思路：

具体做法：

• step 1：从链表数组的首和尾开始，每次划分从中间开始划分，划分成两半，得到左边$n/2$个链表和右边$n/2$个链表。
• step 2：继续不断递归划分，直到每部分链表数为1.
• step 3：将划分好的相邻两部分链表，按照两个有序链表合并的方式合并，合并好的两部分继续往上合并，直到最终合并成一个链表。

代码：

     ListNode* Merge(ListNode* pHead1, ListNode* pHead2){//申请一个哨兵位ListNode* head = new ListNode(0);ListNode* cur = head;while(pHead1 != nullptr && pHead2 != nullptr){if(pHead1->val <= pHead2->val){cur->next = pHead1;cur = cur->next;pHead1 = pHead1->next;}else{cur->next = pHead2;cur = cur->next;pHead2 = pHead2->next;}}//p1未完的情况while(pHead1 != nullptr){cur->next = pHead1;cur = cur->next;pHead1 = pHead1->next;}//p2未完的情况while(pHead2 != nullptr){cur->next = pHead2;cur = cur->next;pHead2 = pHead2->next;}return head->next;}ListNode* DivideMerge(vector<ListNode*> & lists, int l, int r){//不存在区间if(l > r) return nullptr;//已到达最小的区间if(l == r) return lists[l];int mid = l + r >> 1;return Merge(DivideMerge(lists, l, mid), DivideMerge(lists, mid + 1, r));}ListNode* mergeKLists(vector<ListNode*>& lists) {return DivideMerge(lists, 0, lists.size() - 1);}

复杂度：

• 时间复杂度：$O(nlo{g}_{2}K)$,其中$n$为所有链表的总节点数，分治为二叉树型递归，最坏情况下二叉树每层合并都是O(N)个节点,因为分治一共有$O(lo{g}_{2}K)$
• 空间复杂度：$O(lo{g}_{2}K)$,最坏的情况需要向下递归$lo{g}_{2}K$层，需要$lo{g}_{2}K$个函数栈帧

方法三：优先队列–>借鉴牛客题解

思路：

如果非要按照归并排序的合并思路，双指针不够用，我们可以直接准备k个指针，每次比较得出k个数字中的最小值，我们可以借助堆，也就是优先队列—>priority_queue来完成这一点。

代码：

   struct cmp{bool operator()(ListNode* a, ListNode* b){return a->val > b->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {//小根堆priority_queue<ListNode*, vector<ListNode*>, cmp> pq;//遍历所有链表的第一个元素,并且把不为空的加入到优先队列for(int i = 0; i < lists.size(); ++i){if(lists[i] != nullptr) pq.push(lists[i]);}ListNode* res = new ListNode(-1);ListNode* cur = res;while(!pq.empty()){//取出最小的元素ListNode* t = pq.top();pq.pop();//链接到尾部cur->next = t;cur = cur->next;//将该链表的下一个指针加入到优先队列if(t->next != nullptr)pq.push(t->next);}return res->next;}

复杂度：

• 时间复杂度：$O(nlo{g}_{2}K)$,其中$n$为所有链表的总节点数，每次加入优先队列的复杂度为$O(lo{g}_{2}K)$
• 空间复杂度：$O(K)$，优先队列的大小为K

这篇关于牛客热题：合并K个升序链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---