题解 | #合并两个排序的链表#

/*
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 head1,p;
        ListNode head2,q;
        if(list1.val>list2.val){
              head1= list2;p = list2;
              head2= list1;q = list1;
        }
        else{
              head1= list1;p = list1;
              head2= list2;q = list2;
        }
        ListNode pre=null;
        while(p!=null&&q!=null){
             if(p.val<=q.val){
                  pre = p;
                  p=p.next;
             }
            else {
               head2 = head2.next;
                q.next=p;
                pre.next=q;
                pre=q;
                q=head2;
            } 
        }
        if(q!=null){
            pre.next=q;
        }
        return head1;
    }
}
// 这题有毒，为什么我用python弄不出来，明明对的呀！！！