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个节点以及本站其他相关专题，如有不足之处，欢迎留言指出，希望对大家有所帮助。感谢朋友们对本站的支持！