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

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
/**
*新建一个链表，谁小就连谁。思路和实现都很简单。
*还可以有一个耗费空间更少的思路，将list2往list1填充。
**/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head1 = list1;
        ListNode head2 = list2;
        ListNode head3 = null;
        ListNode cur;
        if(head1==null) return list2;
        if(head2==null) return list1;
        if(head1.val<head2.val){
            head3 = head1;
            head1 = head1.next;
        }else{
            head3 = head2;
            head2 = head2.next;
        }
        cur = head3;
        while(head1!=null && head2!=null){
            if(head1.val<head2.val){
                    cur.next = head1;
                    head1 = head1.next;
            }else{
                    cur.next = head2;
                    head2 = head2.next;
            }
            cur = cur.next;
        }
        if(head1==null){
            cur.next = head2;
        }else{
            cur.next = head1;
        }
        return head3;
    }
}