16.合并两个排序的链表 Java
2024-10-06 19:31:10
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路
两种解法：递归和非递归
参考代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
//递归解法
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null)
return list2;
else if(list2 == null)
return list1;
ListNode mergehead = null;
if(list1.val <= list2.val){
mergehead = list1;
mergehead.next = Merge(list1.next,list2);
}else{
mergehead = list2;
mergehead.next = Merge(list1, list2.next);
}
return mergehead;
}
}
//非递归解法
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null)
return list2;
else if(list2 == null)
return list1;
ListNode mergehead = null;
if(list1.val <= list2.val){
mergehead = list1;
list1 = list1.next;
}else{
mergehead = list2;
list2 = list2.next;
}
ListNode cur = mergehead;
while(list1 != null && list2 != null){
if(list1.val <= list2.val){
cur.next = list1;
list1 = list1.next;
}else{
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
if(list1 == null)
cur.next = list2;
else if(list2 == null)
cur.next = list1;
return mergehead;
}
}
同时有一个和这个题类似的题
题目:合并K个排序链表
题目描述
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
思路
想办法转成合并两个排序链表再做
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0){
return null;
}
else if(lists.length==1){
return lists[0];
}
else if(lists.length==2){
return mergeTwoList(lists[0],lists[1]); }else{
ListNode[] l1=new ListNode[lists.length/2];
ListNode[] l2=new ListNode[lists.length-lists.length/2];
for(int i=0;i<lists.length;i++){
if(i<lists.length/2)
l1[i]=lists[i];
else
l2[i-lists.length/2]=lists[i];
}
return mergeTwoList(mergeKLists(l1),mergeKLists(l2));
}
}
public ListNode mergeTwoList(ListNode l1,ListNode l2){
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
if(l1.val>=l2.val){
l2.next=mergeTwoList(l1,l2.next);
return l2;
}else{
l1.next=mergeTwoList(l1.next,l2);
return l1;
} }
}
最新文章
- 使用Aspose.Cells 根据模板生成excel里面的 line chart
- iOS图片拉伸
- HDU_2025——查找最大的字母
- 比较两个data日期之间的天数相差
- 深入浅出Node.js (1) - Node简介
- js面向对象+一般方法的选项卡
- 持续集成环境Gitlab-CI的官方安装过程解析
- php常用数学函数
- CodeForces 625D Finals in arithmetic
- Lamp环境下设置绑定apache域名
- java 分页导出百万级数据到excel
- 01_MyBatis EHCache集成及所需jar包,ehcache.xml配置文件参数配置及mapper中的参数配置
- flask模板应用-javaScript和CSS中jinja2
- oo作业总结(二)
- Gradle 实战（1）—— 配置环境变量
- 在main函数前后执行的函数之 C语言
- Redis源代码分析（三十五）--- redis.c服务端的实现分析（2）
- 使用dshow抓取摄像头数据时，回调函数时间为0的问题
- Android ADB命令基本常用操作
- 检测你的php代码执行效率
热门文章
- win10下面opencv安装
- LINQ 多条件join on
- vue组件常用传值
- zxx.cms.app 开发中的一些git命令
- 一个SAP顾问的回忆：我过去很胖!
- vue-element-admin 之改变登录界面input的光标颜色
- 《数字图像处理（MATLAB）》冈萨雷斯
- springboot Invalid character found in the request target. The valid characters are defined in RFC 7230 and RFC 3986
- 一周死磕fastreport ----ASP.NET （三）
- 009.增删查改语法（sql实例）