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

/*
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 pre = new ListNode(-1);
        ListNode res = pre;

        //两个链表合并，首先想到是双指针
        //定义list1， list2的指针分别是 p1,p2
        ListNode p1 = list1;
        ListNode p2 = list2;

        if(list1!=null&&list2==null)
            return list1;
        else if(list1==null&&list2!=null)
            return list2;
        else if(list1==null&&list2==null)
            return null;

        //遍历list1， list2
        while(p1!=null && p2!=null){
            //当list的值小时，
            if(p1.val < p2.val){
                //将此值(这里是list1)加到pre后
                pre.next = p1;
                 //pre前移
                pre = pre.next;
                //p1前移
                p1 = p1.next;
                //当list1已经移动完毕，则需要将list2剩下的节点全部加到尾部即可
                if(p1==null){
                    pre.next = p2;
                }               
            }else if(p1.val > p2.val){
                pre.next = p2;
                pre = pre.next;
                p2 = p2.next;    
                if(p2==null){
                    pre.next = p1;
                }             
            }else{
                pre.next =p1;
                p1 = p1.next;
                pre = pre.next;
                pre.next =p2;
                p2 = p2.next;
                pre = pre.next;
            }
        }
        return res.next;
    }
}

双指针比较两个链表，依次找出小的节点，将找出的节点放到新的链表中。

如果遇到相同的值，则依次加到新的链表中。