Java编程实现递增排序链表的合并
题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
解答:
/* 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; //判断到某个链表为空就返回另一个链表。如果两个链表都为空呢?没关系,这时候随便返回哪个链表,不也是空的吗? if(list2==null)return list1; ListNode list0=null;//定义一个链表作为返回值 if(list1.val<list2.val){//判断此时的值,如果list1比较小,就先把list1赋值给list0,反之亦然 list0=list1; list0.next=Merge(list1.next, list2);//做递归,求链表的下一跳的值 } else{ list0=list2; list0.next=Merge(list1, list2.next); } return list0; } }
简化一下,用那个三目运算符:
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null) return list2; if(list2==null) return list1; ListNode head; list0= list1.val>list2.val?list2:list1; list0.next = list1.val>list2.val?Merge(list1,list2.next):Merge(list1.next,list2); return list0; } }
据说这道题面试的时候经常考,因为它跟斐波那契数列问题一样有递归和非递归两种解法,上面说了递归的解法,下面再来讲下非递归的解法:
/* 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; if(list2 == null ) return list1; ListNode tmp1 = list1; ListNode tmp2 = list2; ListNode head = new ListNode(0); //这里不能把返回链表赋值为null,因为下一行马上就要把它赋值给另一链表,得让它在内存里有位置才行 ListNode headptr = head; while(tmp1 != null && tmp2!=null){ if(tmp1.val <= tmp2.val) { head.next=tmp1; head = head.next; tmp1 = tmp1.next; } else{ head.next=tmp2; head = head.next; tmp2=tmp2.next; } } //其中一个链表已经跑到头之后,继续单链表的合并 while(tmp1 != null){ head.next = tmp1; head = head.next; tmp1= tmp1.next; } while(tmp2 != null){ head.next = tmp2; head = head.next; tmp2= tmp2.next; } head = headptr.next; return head; } }
总结
以上就是本文关于Java编程实现递增排序链表的合并的全部内容,感兴趣的朋友可以参阅:Java编程实现从尾到头打印链表代码实例、Java编程删除链表中重复的节点问题解决思路及源码分享、Java输出链表倒数第k个节点以及本站其他相关专题,如有不足之处,欢迎留言指出,希望对大家有所帮助。感谢朋友们对本站的支持!
上一篇:归并算法之有序数组合并算法实现
栏 目:Java编程
下一篇:判断二叉树是否为完全二叉树的实例
本文标题:Java编程实现递增排序链表的合并
本文地址:https://www.xiuzhanwang.com/a1/Javabiancheng/8462.html
您可能感兴趣的文章
- 01-10Java咖啡馆(1)——叹咖啡
- 01-10Java Socket编程(三) 服务器Sockets
- 01-10Java进阶:Struts多模块的技巧
- 01-10Java Socket编程(一) Socket传输模式
- 01-10Java Socket编程(二) Java面向连接的类
- 01-10Java运行时多态性的实现
- 01-10Java经验点滴:处理没有被捕获的异常
- 01-10Java Socket编程(四) 重复和并发服务器
- 01-10Java中的浮点数分析
- 01-10面向对象编程:Java中的抽象数据类型
阅读排行
本栏相关
- 01-10Java咖啡馆(1)——叹咖啡
- 01-10JVM的垃圾回收机制详解和调优
- 01-10Java Socket编程(三) 服务器Sockets
- 01-10Java进阶:Struts多模块的技巧
- 01-10J2SE 1.5版本的新特性一览
- 01-10Java Socket编程(一) Socket传输模式
- 01-10Java运行时多态性的实现
- 01-10Java Socket编程(二) Java面向连接的类
- 01-10Java Socket编程(四) 重复和并发服务
- 01-10Java经验点滴:处理没有被捕获的异常
随机阅读
- 08-05dedecms(织梦)副栏目数量限制代码修改
- 08-05DEDE织梦data目录下的sessions文件夹有什
- 01-11Mac OSX 打开原生自带读写NTFS功能(图文
- 01-11ajax实现页面的局部加载
- 01-10使用C语言求解扑克牌的顺子及n个骰子
- 04-02jquery与jsp,用jquery
- 01-10delphi制作wav文件的方法
- 01-10C#中split用法实例总结
- 01-10SublimeText编译C开发环境设置
- 08-05织梦dedecms什么时候用栏目交叉功能?