【力扣LeetCode】23 合并K个排序链表

2024-08-28 22:38

本文主要是介绍【力扣LeetCode】23 合并K个排序链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述(难度难)

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

链接

https://leetcode-cn.com/problems/merge-k-sorted-lists/

思路

比较好的两种思路
1、与合并两个有序链表一样,K个链表一起从头往尾走,每次选取K个链表中指针指向位置的最小值,这个最小值使用优先队列维护较为合适。
2、链表之间两两合并,可复用两个有序链表合并的代码。

  • 从第一个链表开始,依次合并后面的链表
  • 分治,第一个链表和第二个链表合并,第三个和第四个合并,如此下去
    在这里插入图片描述
    显然,分治算法是很不错的,在这里本文采用这种方法。

代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.size() == 0){return NULL;}if(lists.size() == 1){return lists[0];}if(lists.size() > 1){vector<ListNode*> liststemp;if(lists.size()%2 == 0){for(int i = 0; i < lists.size(); i+=2){ListNode* ans = mergeTwoLists(lists[i], lists[i+1]);liststemp.push_back(ans);}lists = liststemp;return mergeKLists(lists);}else{// 这里是 i < lists.size()-1 有所怀疑没有仔细确认导致浪费了一点时间查错for(int i = 0; i < lists.size()-1; i+=2){ListNode* ans = mergeTwoLists(lists[i], lists[i+1]);liststemp.push_back(ans);}liststemp.push_back(lists[lists.size()-1]);lists = liststemp;return mergeKLists(lists);}}return NULL;}ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* ans = NULL;if(l1 == NULL && l2 == NULL){return NULL;}else if(l1 == NULL){return l2;}else if(l2 == NULL){return l1;}else{ListNode* t1 = l1;ListNode* t2 = l2;if(t1->val < t2->val){ans = t1;t1 = t1->next;}else{ans = t2;t2 = t2->next;}ListNode* tans = ans;while(t1&&t2){if(t1->val < t2->val){tans->next = t1;t1 = t1->next;tans = tans->next;}else{tans->next = t2;t2 = t2->next;tans = tans->next;}}while(t1){tans->next = t1;t1 = t1->next;tans = tans->next;}while(t2){tans->next = t2;t2 = t2->next;tans = tans->next;}}return ans;}
};

debug代码:

#include <bits/stdc++.h>
using namespace std;struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}};class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.size() == 0){return NULL;}if(lists.size() == 1){return lists[0];}if(lists.size() > 1){vector<ListNode*> liststemp;if(lists.size()%2 == 0){for(int i = 0; i < lists.size(); i+=2){ListNode* ans = mergeTwoLists(lists[i], lists[i+1]);liststemp.push_back(ans);}lists = liststemp;return mergeKLists(lists);}else{for(int i = 0; i < lists.size()-1; i+=2){ListNode* ans = mergeTwoLists(lists[i], lists[i+1]);liststemp.push_back(ans);}liststemp.push_back(lists[lists.size()-1]);lists = liststemp;return mergeKLists(lists);}}return NULL;}ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* ans = NULL;if(l1 == NULL && l2 == NULL){return NULL;}else if(l1 == NULL){return l2;}else if(l2 == NULL){return l1;}else{ListNode* t1 = l1;ListNode* t2 = l2;if(t1->val < t2->val){ans = t1;t1 = t1->next;}else{ans = t2;t2 = t2->next;}ListNode* tans = ans;while(t1&&t2){if(t1->val < t2->val){tans->next = t1;t1 = t1->next;tans = tans->next;}else{tans->next = t2;t2 = t2->next;tans = tans->next;}}while(t1){tans->next = t1;t1 = t1->next;tans = tans->next;}while(t2){tans->next = t2;t2 = t2->next;tans = tans->next;}}return ans;}
};int main()
{Solution s;ListNode* l11 = new ListNode(1);ListNode* l12 = new ListNode(4);ListNode* l13 = new ListNode(5);l11->next = l12;l12->next = l13;while(l11){cout << l11->val << endl;l11 = l11->next;}ListNode* l21 = new ListNode(1);ListNode* l22 = new ListNode(3);ListNode* l23 = new ListNode(4);l21->next = l22;l22->next = l23;ListNode* l31 = new ListNode(2);ListNode* l32 = new ListNode(6);l31->next = l32;vector<ListNode*> test;test.push_back(l11);test.push_back(l21);test.push_back(l31);ListNode* ans = s.mergeKLists(test);while(ans){cout << ans->val << " ";ans = ans->next;}return 0;
}

这篇关于【力扣LeetCode】23 合并K个排序链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1116086

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

安卓链接正常显示,ios#符被转义%23导致链接访问404

原因分析: url中含有特殊字符 中文未编码 都有可能导致URL转换失败,所以需要对url编码处理  如下: guard let allowUrl = webUrl.addingPercentEncoding(withAllowedCharacters: .urlQueryAllowed) else {return} 后面发现当url中有#号时,会被误伤转义为%23,导致链接无法访问

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L