Java编程实现递增排序链表的合并
题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
解答:
/* publicclassListNode{ intval; ListNodenext=null; ListNode(intval){ this.val=val; } }*/ publicclassSolution{ publicListNodeMerge(ListNodelist1,ListNodelist2){ if(list1==null)returnlist2;//判断到某个链表为空就返回另一个链表。如果两个链表都为空呢?没关系,这时候随便返回哪个链表,不也是空的吗? if(list2==null)returnlist1; ListNodelist0=null;//定义一个链表作为返回值 if(list1.val简化一下,用那个三目运算符:
publicclassSolution{ publicListNodeMerge(ListNodelist1,ListNodelist2){ if(list1==null) returnlist2; if(list2==null) returnlist1; ListNodehead; list0=list1.val>list2.val?list2:list1; list0.next=list1.val>list2.val?Merge(list1,list2.next):Merge(list1.next,list2); returnlist0; } }据说这道题面试的时候经常考,因为它跟斐波那契数列问题一样有递归和非递归两种解法,上面说了递归的解法,下面再来讲下非递归的解法:
/* publicclassListNode{ intval; ListNodenext=null; ListNode(intval){ this.val=val; } }*/ publicclassSolution{ publicListNodeMerge(ListNodelist1,ListNodelist2){ if(list1==null) returnlist2; if(list2==null) returnlist1; ListNodetmp1=list1; ListNodetmp2=list2; ListNodehead=newListNode(0); //这里不能把返回链表赋值为null,因为下一行马上就要把它赋值给另一链表,得让它在内存里有位置才行 ListNodeheadptr=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; returnhead; } }总结
以上就是本文关于Java编程实现递增排序链表的合并的全部内容,感兴趣的朋友可以参阅:Java编程实现从尾到头打印链表代码实例、Java编程删除链表中重复的节点问题解决思路及源码分享、Java输出链表倒数第k个节点以及本站其他相关专题,如有不足之处,欢迎留言指出,希望对大家有所帮助。感谢朋友们对本站的支持!