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

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // 如果两个链表有一个为空，则直接返回另一个非空链表，有点像之前的合并区间，利用了双指针
        // 先定义一个哨兵节点
        ListNode dummy = new ListNode(0) ;
        ListNode curr = dummy;
        // 两个链表还没有结束
        while(list1 != null  && list2 != null){
            if(list1.val < list2.val){
                curr.next  = list1;
                list1 = list1.next;
            }else{
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }
        curr.next = list1 != null ? list1 : list2;
        return dummy.next;
    
    }
}

题目思路比较好理解，跟之前数组的合并区间是一样的。

这里面需要新定义一个哨兵节点，它的第一个值不管，但是不能为null，否则不能next。

然后当两个链表的值都存在，不为null的时候，比较值，把较小的给dummy，由于dummy保存了头节点，还需要定义一个节点来记录当前节点，curr。赋值给curr.next之后，要记得把赋值的节点往后挪动一下，并且curr自己在一次循环后也要进行挪动。

当有节点为null的时候，直接把不为null的节点赋值给curr.next即可。

最后返回dummy.next