java编程题之合并两个排序的链表
本文实例为大家分享了java合并两个排序的链表，供大家参考，具体内容如下
/**
*
*剑指offer编程题（JAVA实现)——第16题：合并两个排序的链表
*
*输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
*
*/
publicclassTest16{
publicstaticListNodeMerge(ListNodelist1,ListNodelist2){
if(list1==null){//首先判断是否有链表为空
returnlist2;
}elseif(list2==null){
returnlist1;
}
ListNodeend1=list1;
ListNodeend2=list2;
ListNodetmp;//end1和end2分别代表两个链表，tmp用于中间合成链表
if(end1.val>end2.val){//把首节点小的链表看作end1
tmp=end1;
end1=end2;
end2=tmp;
}else{
}
ListNodenewNode=end1;//用于最终返回的链表首节点
while(end1.next!=null&&end2.next!=null){//将链表2中的元素插入链表1中合适的位置
if(end1.val<=end2.val&&end1.next.val>=end2.val){
tmp=end2.next;
end2.next=end1.next;
end1.next=end2;
end1=end2;
end2=tmp;
}else{
end1=end1.next;
}
}
if(end1.next==null){//如果链表1到尾节点了则直接连接剩下的链表2中的首节点
end1.next=end2;
returnnewNode;
}else{
if(end1.next!=null&&end2.next==null){//如果链表2到尾节点了则将链表2中所剩下的最后一个节点插入链表1
while(end2!=null){
if(end1.val<=end2.val&&end1.next.val>=end2.val){
end2.next=end1.next;
end1.next=end2;
break;
}else{
end1=end1.next;
if(end1.next==null){//链表2最后的节点最大
end1.next=end2;
break;
}
}
}
}
returnnewNode;
}
}
publicstaticvoidmain(String[]args){
ListNodelist1=newListNode(1);
list1.next=newListNode(3);
list1.next.next=newListNode(5);
ListNodelist2=newListNode(2);
list2.next=newListNode(4);
list2.next.next=newListNode(6);
System.out.println(Merge(list2,list1));
}
//链表
publicstaticclassListNode{
intval;
ListNodenext=null;
ListNode(intval){
this.val=val;
}
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。