题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解法://递归解法
public class MixLink {
/*
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 list3 = null;
if(list1.val<list2.val){
list3 = list1;
list3.next = Merge(list1.next,list2);
}else if(list1.val>=list2.val){
list3 = list2;
list3.next = Merge(list1,list2.next);
}
return list3;
}
}
解法： 非递归
while(list1!=null&&list2!=null){ if(list1.val<list2.val){ if(list3==null){ list3 = list1; }else{ list3.next = list1; list3 = list3.next; } list1 = list1.next; }else if(list1.val>list2.val){ if(list3 == null){ list3 = list2; }else{ list3.next = list2; list3 = list3.next; } list2 = list2.next; } } if(list1==null){ list3.next= list2; } if(list2 == null){ list3.next = list1; } return list3;原文：http://www.cnblogs.com/tandy/p/5443872.html