这篇文章主要介绍了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递增排序链表合并的实现方式的详细内容,更多请关注其它相关文章!
当明知不可挽回,唯一补偿的方法就是怀念,