当前位置:网站首页>Leetcode刷题——23. 合并K个升序链表
Leetcode刷题——23. 合并K个升序链表
2022-08-02 19:23:00 【lonelyMangoo】
21. 合并两个有序链表
先看看这题合并两个有序链表
思路:找出两个链表中较小的元素链接到结果链表,当有一个链表为空时,另一个直接连接到目标结尾即可。
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode listNode = new ListNode();
ListNode res = listNode;
while (list1!=null && list2!=null){
int val1= list1.val;
int val2= list2.val;
if(val1<val2){
listNode.next=list1;
list1=list1.next;
}else{
listNode.next=list2;
list2=list2.next;
}
listNode=listNode.next;
}
if(list1!=null){
listNode.next=list1;
}
if(list2!=null){
listNode.next=list2;
}
return res.next;
}
23. 合并K个升序链表
再看这道题:
23. 合并K个升序链表
首先第一思路是就是两两合并。
代码如下:
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0){
return null;
}
if(lists.length==1){
return lists[0];
}
for (int i = 1; i < lists.length; i++) {
lists[i]=mergeTwoLists(lists[i],lists[i-1]);
}
return lists[lists.length-1];
}
这样实现起来虽然简单,但是时间效率很差,因为合并是O(n),每次都遍历和之前的合并,时间复杂度也是O(n),所以之间复杂度是O(n^2)
归并排序
其实很容易想到,里面有很多冗余的步骤,可以两两合并,也就是我们熟悉的归并排序。
在我们用数组排序的时候,创建一个新的数组,每次归并,都对指定指定位置的元素修改。
而这里链表则是每次都返回排序好的链表进行合并。
在归并的底层是单个元素,所以当left == right的时候,直接返回当前元素。
代码:
private static ListNode mergeLists(ListNode[] lists,int left ,int right) {
int mid = (left+right)/2;
if(left == right){
return lists[left];
}
if(left<right){
ListNode listNode1 = mergeLists(lists, left, mid);
ListNode listNode2 = mergeLists(lists, mid + 1, right);
return mergeTwoLists(listNode1,listNode2);
// mergeTwoLists(lists[left],l)
}
return null;
}
这样的话时间复杂度就变成了O(n*logn)
边栏推荐
- 扫码预约 | 观看Apache Linkis数据处理实践以及计算治理能力
- MOSN 反向通道详解
- 实现客户服务自助,打造产品知识库
- Geoserver+mysql+openlayers
- Brain-computer interface 003 | Musk said that he has realized a virtual self-dialogue with the cloud, and related concept shares have risen sharply
- 使用位运算实现加减乘除(+、-、*、/)及比较器的用法
- Geoserver+mysql+openlayers2
- Detailed explanation of common examples of dynamic programming
- 2022-07-28
- geoserver+mysql+openlayers问题点
猜你喜欢
安装Mac版Mysql卡在Installation阶段,彻底清理mysql并重装mysql
Detailed explanation of common examples of dynamic programming
研发了 5 年的时序数据库,到底要解决什么问题?
4KMILES加入艾盛集团,以更强劲的数字商务能力,加速中国跨境电商的全域全效增长
thinkphp框架5.0.23安全更新问题-漏洞修复-/thinkphp/library/think/App.php具体怎么改以及为什么要这么改
es 读流程源码解析
2022-07-27
解析Collection接口中的常用的被实现子类重写的方法
脑机接口003 | 马斯克称已实现与云端的虚拟自己对话,相关概念股份大涨
实现客户服务自助,打造产品知识库
随机推荐
SQL-UDT是什么功能?
我靠这套笔记自学,拿下字节50万offer....
leetcode刷题记录:7.整数反转,8.字符串转整数,9.回文数
项目分析(复杂嵌入式系统设计)
元旦快乐(2022)
Therapy | How to Identify and Deal with Negative Thoughts
Nature Microbiology综述:聚焦藻际--浮游植物和细菌互作的生态界面
所谓武功再高也怕菜刀-分区、分库、分表和分布式的优劣
简单有效又有用的关闭antimalware service executable的方法·备份记录
2022-07-26
SQL server有什么认证吗?
分享一个 web 应用版本监测 (更新) 的工具库
【心理学 · 人物】第一期
我用这一招让团队的开发效率提升了 100%!
Fetch 请求不转换BLOB正常显示GBK编码的数据
es 读流程源码解析
清除浮动与BFC
JVM内存和垃圾回收-05.虚拟机栈
JVM内存和垃圾回收-04.程序计数器(PC寄存器)
【LeetCode】622. 设计循环队列