当前位置:网站首页>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)
边栏推荐
- 译出我精彩 | 7月墨力翻译计划获奖名单公布
- 【学习日记】win64配置openni的vs2022编译环境
- EMQX Newsletter 2022-07|EMQX 5.0 正式发布、EMQX Cloud 新增 2 个数据库集成
- 线性表(顺序表和链表)
- Detailed explanation of common examples of dynamic programming
- Golang swagger :missing required param comment parameters
- ALV报表学习总结
- 一些不错的博主
- 技术分享 | Apache Linkis 快速集成网页IDE工具 Scriptis
- 基于OpenGL的冰川与火鸟(光照计算模型、视景体、粒子系统)
猜你喜欢
随机推荐
golang刷leetcode 数学(1) 丑数系列
软考 ----- UML设计与分析(下)
Dynamically generate different types of orders, how do I deposit to mongo database?
ShardingSphere-proxy +PostgreSQL实现读写分离(静态策略)
2022-07-28
Geoserver+mysql+openlayers2
看完这篇,轻松get限流!
JVM内存和垃圾回收-06.本地方法栈
项目分析(复杂嵌入式系统设计)
Brain-computer interface 003 | Musk said that he has realized a virtual self-dialogue with the cloud, and related concept shares have risen sharply
Mysql安装流程 【压缩版】
Therapy | How to Identify and Deal with Negative Thoughts
shell:条件语句
扫码预约 | 观看Apache Linkis数据处理实践以及计算治理能力
Caldera(一)配置完成的虚拟机镜像及admin身份简单使用
idea 配置resin
如何ES源码中添加一个自己的API 流程梳理
MySQL安装时一直卡在starting server
聊一聊 AS 的一些好用的功能
MySQL安装配置教程(超级详细、保姆级)