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

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    /*
    分别使用两个指针来遍历两个链表
    遍历结束的条件当这两个指针有一个等于null
    每次遍历把节点值小的节点加入到新的链表中,然后指针后移
    遍历结束
    把没有便利完的链表加入新链表末尾
    返回新链表
    */
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode p = list1,q = list2;
        ListNode temp = null; // 用于指向需要加入新链表的节点
        
        ListNode returnList = new ListNode(-1); // 返回的链表的头节点
        ListNode tail = returnList; // 链表的尾节点,用于尾插入
        
        while(p != null && q != null){
            if(p.val <= q.val){
                temp = p; // 把节点拿出来
                p = p.next; // 指针后移
                // 插入节点
                temp.next = tail.next;
                tail.next = temp;
                // 尾指针后移
                tail = tail.next;
            }else{
                temp = q; // 把节点拿出来
                q = q.next; // 指针后移
                // 插入节点
                temp.next = tail.next;
                tail.next = temp;
                // 尾指针后移
                tail = tail.next;
            }
        }
        
        if(p != null){
            // 把剩余未遍历到的部分加入新链表
            tail.next = p;
        }
        
        if(q != null){
            // 把剩余未遍历到的部分加入新链表
            tail.next = q;
        }
        
        return returnList.next; // 返回首节点开始的部分
    }
}