将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode pre=new ListNode(-1);
        ListNode head=pre;
        while(list1!=null&list2!=null){
            if(list1.val>list2.val){
                head.next=list2;
                list2=list2.next;
            }else{
                head.next=list1;
                list1=list1.next;
            }
            head=head.next;
        }
        head.next=list1==null?list2:list1;
        return pre.next;
    }
}