输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

//方案一：

public class Solution {

public ListNode Merge(ListNode list1,ListNode list2) {

    ListNode node=new ListNode(-1);
    ListNode temp=node;

    while(list1!=null&&list2!=null){
        if(list1.val<list2.val)
        {
            temp.next=list1;
            temp=temp.next;
            list1=list1.next;
        }else{
            temp.next=list2;
            temp=temp.next;
            list2=list2.next;
        }
    }

    if(list1!=null)
        temp.next=list1;

    if(list2!=null)
        temp.next=list2;

    return node.next;

}

}

//方案二：

public class Solution {

public ListNode Merge(ListNode list1,ListNode list2) {
    ListNode node=new ListNode(-1);
    ListNode temp=node;

    while(list1!=null&&list2!=null){
        if(list1.val<list2.val)
        {
            temp.next=new ListNode(list1.val);
            temp=temp.next;
            list1=list1.next;
        }else{
            temp.next=new ListNode(list2.val);
            temp=temp.next;
            list2=list2.next;
        }
    }

    while(list1!=null){
        temp.next=new ListNode(list1.val);
        temp=temp.next;
        list1=list1.next;
    }

    while(list2!=null){
        temp.next=new ListNode(list2.val);
        temp=temp.next;
        list2=list2.next;
    }

    return node.next;

}

}

//方案三

public class Solution {

public ListNode Merge(ListNode list1,ListNode list2) {

    if(list1==null)
        return list2;
    if(list2==null)
        return list1;

    ListNode res=null;

    if(list1.val<list2.val){
        res=list1;
        res.next=Merge(list1.next,list2);
    }else{
        res=list2;
        res.next=Merge(list1,list2.next);
    }

    return res;

}

}

//方案四

public class Solution {

public ListNode Merge(ListNode list1,ListNode list2) {
    if(list1==null)
        return list2;
    if(list2==null)
        return list1;

   ListNode firstNode=null;
   ListNode temp=null;

   while(list1!=null&&list2!=null){

       if(list1.val<list2.val){
           if(firstNode==null){
               firstNode=list1;
               temp=firstNode;
           }
           else{
           temp.next=list1;
           temp=temp.next;
           }
           list1=list1.next;
       }else{
           if(firstNode==null){
               firstNode=list2;
               temp=firstNode;
           }else{
           temp.next=list2;
           temp=temp.next;
           }
           list2=list2.next;
       }
   }

    if(list1!=null)
        temp.next=list1;
    if(list2!=null)
        temp.next=list2;


    return firstNode;

}

}

//如果要求不能改变传入的变量（引用）选方案二，其余的方案都和传入的变量有关，从代码简洁选方案三，方案4是方案3的非递归版本