23. 合并K个升序链表
2023-04-18 16:11:31 时间
思路:
前面我们已经知道两个链表如何合并了,那么我们首先想到的是可以循环着合并两个链表,但是这样复杂度比较高. 考虑优化方法,用分治的方法进行合并。 将链表数组不断分裂,然后合并,这样第一轮合并,k个链表就被合并成了k/2个链表,平均长度为2n/k,然后是k/4,k/8个链表等,重复这一过程,直到得到最终的有序链表。
这样做的好处就是合并的链表数目要少很多了,分支合并剩下的链表会越来越少的。
代码:
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merger(lists, 0, lists.length - 1);
}
private ListNode merger(ListNode[] lists, int l, int r) {
if (l == r) {
return lists[l];
}
if (l > r) {
return null;
}
//右移一位相当于除2
int mid=(l+r)>>1;
return mergeTwoLists(merger(lists,l,mid),merger(lists,mid+1,r));
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode curr = pre;
while (l1 != null || l2 != null) {
if (l1 == null) {
curr.next = l2;
return pre.next;
}
if (l2 == null) {
curr.next = l1;
return pre.next;
}
if (l1.val < l2.val) {
curr.next = l1;
curr = curr.next;
l1 = l1.next;
} else {
curr.next = l2;
curr = curr.next;
l2 = l2.next;
}
}
return pre.next;
}
}
相关文章
- 开源漏洞数量增长33%!企业安全债务不堪重负丨行业数据
- AcWing244.谜一样的牛
- Kubernetes监控手册04-监控Kube-Proxy
- AcWing291.蒙德里安的梦想题解
- 在同一台主机启动多个FreeSWITCH实例
- Codeforces 983 D Arkady and Rectangles 题解
- 统一异常处理——BlockException
- AcWing.7 混合背包问题
- 第三章 --------------------XAML的属性和事件
- AcWing241. 楼兰图腾
- MAUI新生5.1-Shell导航视觉层次结构
- 2022年终记忆--雅俗-平凡--初心
- (二)elasticsearch 源码目录
- 可持久化线段树详解(基础)
- MAUI新生6.2-布局类控件难点:FlexLayout、BindableLayout、StateContainer
- Sentinel的规则
- cmake-4
- Kubernetes监控手册03-宿主监控实操
- AcWing1134/洛谷P1144 最短路计数
- AcWing1131. 拯救大兵瑞恩