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

采用插入法：首先找出两个链表哪个作为返回链表的表头（节点值较小的那个），然后设置一个前驱pre，根据值的大小比较进行合适的位置插入即可。这个方法记录了每次插入的前驱，每次进行插入时无需遍历链表，因此时间复杂度为O(n)

    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;
    }
}