链表合并

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0 \le n \le 10000≤n≤1000，-1000 \le 节点值 \le 1000−1000≤节点值≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}

思路：

双指针：这道题既然两个链表已经是排好序的，都是从小到大的顺序，那我们要将其组合，可以使用归并排序的思想：每次比较两个头部，从中取出最小的元素，然后依次往后。这样两个链表依次往后，我们肯定需要两个指针同方向访问才能实现。

具体过程：

• step 1：判断空链表的情况，只要有一个链表为空，那答案必定就是另一个链表了，就算另一个链表也为空。
• step 2：新建一个空的表头后面连接两个链表排序后的节点，两个指针分别指向两链表头。
• step 3：遍历两个链表都不为空的情况，取较小值添加在新的链表后面，每次只把被添加的链表的指针后移。
• step 4：遍历到最后肯定有一个链表还有剩余的节点，它们的值将大于前面所有的，直接连在新的链表后面即可。

function ListNode(x){
    this.val = x;
    this.next = null;
}
function Merge(pHead1, pHead2)
{
    // write code here
    if (!pHead1) return pHead2;
    if (!pHead2) return pHead1;
    let cur=new ListNode(0);
    let head=cur;
    while(pHead1 && pHead2){
        if (pHead1.val <=pHead2.val){
            cur.next = pHead1;
            pHead1=pHead1.next;
        }
        else {
            cur.next = pHead2;
            pHead2=pHead2.next;
        }
        cur=cur.next;
    }
    if (pHead1) cur.next = pHead1;
    else cur.next = pHead2;
    
    return head.next;
    
}
module.exports = {
    Merge : Merge
};