解法1：双指针。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(null==list1) return list2;
        if(null==list2) return list1;
        ListNode pHead=new ListNode();
        ListNode t=pHead;
        while(null!=list1 && null!=list2){
            if(list1.val<=list2.val){
                t.next=list1;
                list1=list1.next;
            }else{
                 t.next=list2;
                list2=list2.next;
               
            }
             t=t.next;
        }
        if(null==list1){
            t.next=list2;
        }
        if(null==list2){
            t.next=list1;
        }
        return pHead.next;
    }
}

解法2：递归。

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(null==list1) return list2;
        if(null==list2) return list1;
        if(list1.val<=list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }
        
    
    }