当前位置:网站首页>每日一题-合并K个升序链表-0722
每日一题-合并K个升序链表-0722
2022-08-05 05:17:00 【菜鸡程序媛】
题目
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
思路
- 采用归并排序的思路,先进行拆解到最小的单位,拆到不能再拆
- 然后再合并,合并成最终的链表
代码
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length <= 0)
return null;
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int left, int right){
if(left == right)
return lists[left];
int mid = left + (right - left) / 2;
//为什么不是left,mid-1和mid,right呢,因为mid取得就是floor(value),如果-1的话,容易造出左侧越界
//拆解到最小的单位
ListNode l1 = merge(lists, left, mid);
ListNode l2 = merge(lists, mid + 1, right);
//进行合并,归并成最终的链表
return mergeTwoLists(l1, l2);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2){
if(l1 == null)
return l2;
if(l2 == null)
return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
边栏推荐
猜你喜欢
随机推荐
单片机按键开发库-支持连击、长按等操作
【UiPath2022+C#】UiPath Switch
读论文- pix2pix
读论文 - Unpaired Portrait Drawing Generation via Asymmetric Cycle Mapping
物联网-广域网技术之NB-IoT
PoE视频监控解决方案
网络信息安全运营方法论 (下)
对象比较
深度学习系列(二)优化器 (Optimization)
表情捕捉的指标/图像的无参考质量评价
LeetCode刷题之第129题
基于STM32F407的WIFI通信(使用的是ESP8266模块)
十、视图解析原理与源码分析
You should write like this
LeetCode刷题之第24题
七、请求处理——Map、Model类型参数处理原理
idea 快速日志
LeetCode刷题之第74题
【ts】typescript高阶:模版字面量类型
基于STM32F4的FFT+测频率幅值相位差,波形显示,示波器,时域频域分析相关工程