DT走过的路

描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： $0\le n\le 1000$0≤n≤1000，$-1000\le \mathrm{节}\mathrm{点}\mathrm{值}\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}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

示例1

输入：

{1,3,5},{2,4,6}

返回值：

{1,2,3,4,5,6}

示例2

输入：

{},{}

返回值：

{}

示例3

输入：

{-1,2,4},{1,3,4}

返回值：

{-1,1,2,3,4,4}

方式一：很自然联想到数组的排序，然后再将数组转成链表

需要注意let head = new ListNode(res[0]); let pre = head; 游标和主链表

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
function Merge( pHead1 ,  pHead2 ) {
    // write code here
    //console.log(pHead1,'pHead1')
    const res = [];
    let p1 = pHead1, p2 = pHead2;
    while(p1){
        res.push(p1.val);
        p1 = p1.next;
    }
    while(p2){
        res.push(p2.val);
        p2 = p2.next;
    }
    res.sort((a,b)=>a-b);
    if(!res.length) return null;
    let head = new ListNode(res[0]);
    let pre = head;
    for(let i=1;i<res.length;i++){
        const curNode = new ListNode(res[i]);
        pre.next = curNode;
        pre = curNode;
    }
    //console.log(head,'head');
    return head;
}
module.exports = {
    Merge : Merge
};

方式二

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
function Merge( pHead1 ,  pHead2 ) {
    // write code here
    //采用链表方式
    const vNode = new ListNode(-1);
    let cur = vNode;
    while(pHead1 && pHead2){
        if(pHead1.val <= pHead2.val){
            cur.next = pHead1;
            pHead1 = pHead1.next;
        }else{
            cur.next = pHead2;
            pHead2 = pHead2.next;
        }
        cur = cur.next;
    }
    cur.next = pHead1 ? pHead1 : pHead2;
    //console.log(vNode);
    return vNode.next;
   
}