首页 > 试题广场 >

合并两个排序的链表

[编程题]合并两个排序的链表
  • 热度指数：1194357 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入两个递增的链表，单个链表的长度为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}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
Javascript
牛客975836981号头像 牛客975836981号
ddddddddd
发表于 2023-05-20 10:51:37 回复(0)
Javascript
勒布_朗詹姆斯头像 勒布_朗詹姆斯

function ListNode(x){
    this.val = x;
    this.next = null;
}
// 1. 创建一个头链表 head = new ListNode(null) 和 当前的链表 cur = head
// 2. head用来返回，cur.next用来添加新的链表
function Merge(pHead1, pHead2) {
  let head = new ListNode(null);
  let cur = head;
  while (pHead1 && pHead2) {
    if (pHead1.val > pHead2.val) {
      cur.next = pHead2;
      pHead2 = pHead2.next;
    } else {
      cur.next = pHead1;
      pHead1 = pHead1.next;
    }
    cur = cur.next;
  }
  let res = pHead1 != null ? pHead1 : pHead2;
  cur.next = res;
  return head.next;
}
module.exports = {
  Merge: Merge,
};
发表于 2022-07-02 16:38:31 回复(0)
Javascript
美英头像 美英 
function ListNode(x){
    this.val = x;
    this.next = null;
}
function Merge(pHead1, pHead2)
{
    // write code here
    if(!pHead1&&!pHead2){
        return null;
    }
    
    let list1=[],list2=[];
    let list=[];
    //console.log(pHead1);
    list1.push(pHead1);
    while(list1.length){
        let node = list1.shift();
        if(node){
            list.push(node.val);
            if(node.next){
                list1.push(node.next);
            }
        }
    }
    list2.push(pHead2);
    while(list2.length){
        let node = list2.shift();
        if(node){
            list.push(node.val);
            if(node.next){
                list2.push(node.next);
            }
        }
    }
    
    list.sort((a,b)=>a-b)
    
    //数组转成链表
    let node=new ListNode(0);
    let tmp = node;
    for(let i=0;i<list.length;i++){
        node.val = list[i];
        if(i!=list.length-1){
           node.next=new ListNode(0);
        }
        node = node.next;
    }
    return tmp;
}
module.exports = {
    Merge : Merge
};

发表于 2021-12-12 10:12:53 回复(0)
Javascript
FoRtCurious头像 FoRtCurious 
function Merge(pHead1, pHead2)
{
    // write code here
    if(pHead1 === null) return pHead2;
    if(pHead2 === null) return pHead1;
    
    if (pHead1.val < pHead2.val) {
        pHead1.next = Merge(pHead1.next,pHead2)
        return pHead1
    } else {
        pHead2.next = Merge(pHead1,pHead2.next)
        return pHead2
    }
}


发表于 2021-12-11 15:20:05 回复(0)
Javascript
牛客140967527号头像 牛客140967527号 
function Merge(pHead1, pHead2)
{
    if (!pHead1) { return pHead2; }
    if (!pHead2) { return pHead1; }
    
    let result = pHead1.val <= pHead2.val ? pHead1 : pHead2;
    let p1 = pHead1, p2 = pHead2, prev = null, v1 = p1.val, v2 = p2.val;

    while (p1 && p2) {
        if (v1 <= v2) {
            let next = p1.next;            
            
            if (prev) { prev.next = p1; }
            p1.next = p2;
            
            prev = p1;
            p1 = next;
            v1 = p1 ? p1.val : v1;
        } else {
            let next = p2.next;            
            
            if (prev) { prev.next = p2; }
            p2.next = p1;
            
            prev = p2;
            p2 = next;
            v2 = p2 ? p2.val : v2;
        }
    }
    
    return result;
}

发表于 2021-12-05 09:21:45 回复(0)
Javascript
♈FourBrother✅已认证♉头像 ♈FourBrother✅已认证♉ 
function Merge(pHead1, pHead2)
{
    // write code here
    let newHead = {
        next: null
    }
    let newCur = newHead
    let cur1 = pHead1
    let cur2 = pHead2
    while(true) {
        if (cur1 && cur2) {
            if (cur1.val < cur2.val) {
              newCur.next = {
                  val: cur1.val,
                  next: null
              }
              newCur = newCur.next
              cur1 = cur1.next  
            } else {
              newCur.next = {
                  val: cur2.val,
                  next: null
              }
              newCur = newCur.next
              cur2 = cur2.next  
            }
        } else if (cur1) {
            newCur.next = cur1
            return newHead.next
        } else if (cur2) {
            newCur.next = cur2
            return newHead.next
        } else return newHead.next
    }
}

发表于 2021-11-19 15:58:28 回复(0)
Javascript
小夏不饿头像 小夏不饿 
//    递归写法 
function Merge(pHead1, pHead2){
   if(!pHead1) return pHead2;
   if(!pHead2) return pHead1;
    if(pHead1.val <= pHead2.val){
        pHead1.next = Merge(pHead1.next,pHead2);
        return pHead1;
    }else {
        pHead2.next = Merge(pHead1,pHead2.next);
        return pHead2;
    }
}


//    非递归写法 
function Merge(pHead1, pHead2){
   if(!pHead1) return pHead2;
   if(!pHead2) return pHead1;
    let head = {
        val: null,
        next: null
    };
    let current = head;
    while (pHead1 && pHead2){
        if(pHead1.val <= pHead2.val){
            current.next = pHead1;
            current = current.next;
            pHead1 = pHead1.next;
        }else {
            current.next = pHead2;
            current = current.next;
            pHead2 = pHead2.next;
        }
    }
    //将未遍历完的链表插到后面
    if(pHead1){
        current.next = pHead1;
    }else{
        current.next = pHead2;
    }
    return head.next;
}

发表于 2021-10-01 15:12:05 回复(0)
Javascript
牛客246205877号头像 牛客246205877号 
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function Merge(pHead1, pHead2)
{
    const arr = [];
    while(pHead1){
        arr.push(pHead1);
        pHead1 = pHead1.next
    }
    while(pHead2){
        arr.push(pHead2);
        pHead2 = pHead2.next
    }
    arr.sort((pre,next) => {
        return pre.val - next.val
    });
    for(let i = 0;i<arr.length;i++){
        arr[i].next = arr[i + 1]
    }
    return arr[0]
}
module.exports = {
    Merge : Merge
};


发表于 2021-09-08 14:49:39 回复(0)
Javascript
小菜鸡的菜头像 小菜鸡的菜
function Merge(pHead1, pHead2)
{
    var ret = new ListNode(0)
    var h=ret
    var h1 = pHead1,h2 = pHead2
    while(h1 && h2){
        if(h1.val>h2.val){
            h.next=h2
            h=h.next
            h2=h2.next
        }else{
            h.next=h1
            h=h.next
            h1=h1.next
        }
    }
    while(h1){
        h.next=h1
        h=h.next
        h1=h1.next
    }
    while(h2){
        h.next=h2
        h=h.next
        h2=h2.next
    }
    return ret.next
}
发表于 2021-08-12 22:18:37 回复(0)
Javascript
木琴要加油头像 木琴要加油 
function Merge(pHead1, pHead2)
{
    // write code here
    if(!pHead1) {
        return pHead2;
    }
    if(!pHead2) {
        return pHead1;
    }
    let arr = [];
    while(pHead1) {
        arr.push(pHead1.val);
        pHead1 = pHead1.next;
    }
    while(pHead2) {
        arr.push(pHead2.val);
        pHead2 = pHead2.next;
    }
    arr.sort((a,b) => (b-a));
    let link = null;
    for(let i = 0;i < arr.length;i++) {
        link = {
            val: arr[i],
            next: link
        }
    }
    return link; 
}
module.exports = {
    Merge : Merge
};

发表于 2021-08-05 15:08:50 回复(0)
Javascript
webchang头像 webchang
使用JavaScript来实现

方法1

  1. 创建一个数组，循环遍历两个链表，将每个节点的值头添加到数组中
  2. 按照从下到大的顺序对数组进行排序
  3. 使用数组中的第一个元素作为值新创建一个ListNode节点作为新链表的头节点
  4. 从第二个元素开始，循环遍历数组，创建节点并添加到新链表中 
function ListNode(x){
    this.val = x;
    this.next = null;
}

function Merge(pHead1, pHead2)
{
    // write code here
    if(pHead1 === null) return pHead2;
    if(pHead2 === null) return pHead1;
    let arr = [];
    while(pHead1) {
        arr.push(pHead1.val);
        pHead1 = pHead1.next;
    }
    while(pHead2) {
        arr.push(pHead2.val);
        pHead2 = pHead2.next;
    }
    arr.sort((a,b) => a - b);
    let newHead = new ListNode(arr[0]);
    let current = newHead;
    for(let i = 1;i < arr.length;i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return newHead;
}
module.exports = {
    Merge : Merge
};

方法2：使用递归 

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function Merge(pHead1, pHead2)
{
    // write code here
    if(!pHead1) return pHead2;
    if(!pHead2) return pHead1;
    if(pHead1.val < pHead2.val) {
        pHead1.next = Merge(pHead1.next, pHead2);
        return pHead1;
    } else {
        pHead2.next = Merge(pHead1, pHead2.next);
        return pHead2;
    }
}
module.exports = {
    Merge : Merge
};

方法3

  1. 创建一个节点作为新链表的头部节点。
  2. 同时循环遍历两个链表，如果pHead1的值小于pHead2的值，就让新头部节点指向pHead1，让pHead1指向下一个节点。如果pHead1的值大于pHead2的值，就让新头部节点指向pHead2，让pHead2指向其下一个节点
  3. 多次执行步骤2，直到pHead1或pHead2为null（表示该链表遍历完了），退出循环
  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 newHead = new ListNode(0);
    let current = newHead;
    while(pHead1 && pHead2) {
        if(pHead1.val < pHead2.val) {
            current.next = pHead1;
            current = current.next;
            pHead1 = pHead1.next;
        } else {
            current.next = pHead2;
            current = current.next;
            pHead2 = pHead2.next;
        }
    }
    
    if(pHead1 === null) {
        current.next = pHead2;
    } else {
        current.next = pHead1;
    }
    return newHead.next;
}
module.exports = {
    Merge : Merge
};

发表于 2021-07-24 17:11:39 回复(0)
JavaScript
别卷啦！头像 别卷啦！
通过递归的方式 依次将两个链表的元素递归进行对比 
function Merge(l1, l2)
{
    // write code here
    if(!l1) return l2;
    if(!l2) return l1;
    if(l1.val <= l2.val) {
        l1.next = Merge(l1.next, l2);
        return l1;
    }else {
        l2.next = Merge(l2.next, l1);
        return l2
    }
}


发表于 2021-07-01 19:09:21 回复(0)
JavaScript
NPC201904301802722头像 NPC201904301802722 
function Merge(pHead1, pHead2)
{
    // write code here
    if(!pHead1 && !pHead2){
        return null
    }
    if(pHead1 &&!pHead2){
        return pHead1
    }
    if(!pHead1 && pHead2){
        return pHead2
    }
   
    
    let pHead3
    if(pHead1.val<pHead2.val){
        pHead3=pHead1
        pHead1=pHead1.next
    }else{
        pHead3=pHead2
        pHead2=pHead2.next
    }
    
    let root=pHead3
    
    while(pHead1 && pHead2){
        if(pHead1.val<pHead2.val){
            pHead3.next=pHead1
            pHead1=pHead1.next
        }else{
            pHead3.next=pHead2
            pHead2=pHead2.next
        }
        pHead3=pHead3.next
    }
    
    
    if(pHead1){
        pHead3.next=pHead1
    }else if(pHead2){
        pHead3.next=pHead2
    }else{
        pHead3.next=null
    }
    return root
}
感觉有点繁琐
发表于 2021-06-15 21:01:41 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function Merge(pHead1, pHead2)
{
    // write code here
    if(!pHead1){
        return pHead2;
    }
    if(!pHead2){
        return pHead1;
    }
    if(pHead1.val <= pHead2.val){
        pHead1.next = Merge(pHead1.next,pHead2);
        return pHead1;
    }else{
        pHead2.next = Merge(pHead1,pHead2.next);
        return pHead2;
    }
    
}

发表于 2021-03-22 11:20:43 回复(0)
JavaScript
bug附体头像 bug附体
javascript:注释比较详细
function Merge(pHead1, pHead2)
{
    // write code here
    //处理特殊情况
    if(pHead1 === null || pHead2 === null){
        return pHead1 || pHead2
    }
    // 整体思路：遍历pHead2,将pHead2的节点插入到pHead1相应的位置
    // prev/current指针指向pHead1链表相邻的两个节点，p指向pHead2的某个节点,node保存p.next,head为头结点，因为头结点可能会发生变化
    let prev = null, current = pHead1, p = pHead2, node = null, head = pHead1
    // 遍历pHead2链表
    while(p != null){
        // 如果目标节点的值大于prev,小于current,就插入到这两者之间
        // 存在特殊情况，因为插入值是可以插到pHead1头结点之前和尾结点之后的，所以会存在prev/current为null的情况
        if((prev === null || p.val >= prev.val) && (current === null || p.val <= current.val )){
            node = p.next
            // 如果prev为空，说明新插入的节点是头结点
            if(prev === null){
                head = p
            }else{
                prev.next = p
            }
            p.next = current
            //此时插入完毕，做指针变化的处理，p指向下一个节点继续判断；由于是非递减列表，所以后续的插入必然是插入到当前新插入的p节点之后，所以才对prev做下面的修改
            //修改prev为当前插入的节点
            prev = p
            // p指向下一个节点
            p = node
        }else{
            // 如果不满足插入条件，则移动prev与current指针
            if(current != null){
                prev = current
                current = current.next
            }
        }
    }
    return head
}
发表于 2020-11-13 14:11:52 回复(0)
JavaScript
咚咚咚，开门，查水表头像 咚咚咚，开门，查水表 
function ListNode(x){
    this.val = x;
    this.next = null;
}
function Merge(pHead1, pHead2)
{
    //输入两个单调递增的链表，输出两个链表合成后的链表(单调不减)。
    if (!pHead1) return pHead2;
    if (!pHead2) return pHead1;
    
    let head, current, p1 = pHead1, p2 = pHead2;
    
    //1.确定新列表的表头head，并初始化current；
    if (p1.val <= p2.val) {
        head = p1;
        p1 = p1.next;
    } else {
        head = p2;
        p2 = p2.next;
    }
    current = head;
    if(p1 == null) {current.next = p2; return head;}
    if(p2 == null) {current.next = p1; return head;}

    //2.开始拼接
    while (p1 != null && p2 != null) {
        if (p1.val <= p2.val) {
            current.next = p1;
            p1 = p1.next;
        } else {
            current.next = p2;
            p2 = p2.next;
        }
        current = current.next;
        if(p1 == null) {current.next = p2; return head;}
        if(p2 == null) {current.next = p1; return head;}
    }
    return head;
}
module.exports = {
    Merge : Merge
};

发表于 2020-09-13 22:35:50 回复(0)
JavaScript
萨弗拉斯的挽歌头像 萨弗拉斯的挽歌 
function ListNode(x){
    this.val = x;
    this.next = null;
}
function Merge(pHead1, pHead2)
{
    // write code here
    if(pHead1 == null){
        return pHead2
    } else if(pHead2 == null){
        return pHead1
    } else if(pHead2 == null && pHead1 == null){
        return null
    } 
    if(pHead1.val<pHead2.val){
        pHead1.next = Merge(pHead1.next,pHead2); //找到更小的进行递归
        return pHead1;
    } else {
        pHead2.next = Merge(pHead2.next,pHead1);
        return pHead2;
    }
    
    
}
module.exports = {
    Merge : Merge
};

发表于 2020-08-25 17:37:05 回复(0)
JavaScript
奕※時＾毀￠头像 奕※時＾毀￠ 
function Merge(pHead1, pHead2)
{
    var a=[];
    while(pHead1){
        a.push(pHead1);
        pHead1=pHead1.next;
    }
    while(pHead2){
        a.push(pHead2);
        pHead2=pHead2.next;
    }
    if(a.length==0)
        return null;
    //  根据val进行排序
    a=a.sort(function(p,q){
        return p.val-q.val;
    })
    for(var i=0;i<a.length-1;i++){
        a[i].next=a[i+1];
    }
    a[a.length-1].next=null;
    return a[0];
}

发表于 2020-04-28 20:00:53 回复(0)
JavaScript
Helianthuswhite头像 Helianthuswhite 
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

/**
 * 我的解题思路：
 * 1.核心思路使用递归，分别对两个链的节点进行大小比较，将小的放在新的链上
 * 2.判断两个链的头节点，将小的放在新链，并移除原链中该节点，进行递归
 * 3.当某个链先走到头时，另一个链的剩余部分全部加入新链，并返回新链
 *
 * @param {*} pHead1 
 * @param {*} pHead2 
 */
function Merge(pHead1, pHead2)
{
    // write code here
    const func = (l, p1, p2) => {
        if (!p1) {
            l.next = p2
            return;
        }
        if (!p2) {
            l.next = p1;
            return;
        }
        if (p1.val > p2.val) {
            l.next = p2;
            func(l.next, p1, p2.next);
        }
        else {
            l.next = p1;
            func(l.next, p1.next, p2);
        }
    };

    let list = {};
    func(list, pHead1, pHead2);
    list = list.next;
    return list;
}

/**
 * 评论区TOP的解题思路：
 * 1.主要有递归和非递归两种解决思路
 * 2.非递归的解决方案利用新的链表和循环来实现
 * 3.我的解题思路相当于递归和非递归的结合版，不够简洁
 * 4.这里增加一种不用额外空间的递归方式
 *
 * @param {*} pHead1 
 * @param {*} pHead2 
 */
function topMerge(pHead1, pHead2) {
    // write code here
    if (!pHead1) {
        return pHead2;
    }
    if (!pHead2) {
        return pHead1;
    }
    if (pHead1.val > pHead2.val) {
        pHead2.next = topMerge(pHead1, pHead2.next);
        return pHead2;
    }
    else {
        pHead1.next = topMerge(pHead1.next, pHead2);
        return pHead1;
    }
}

发表于 2020-03-01 14:00:23 回复(0)
提交观点

问题信息

链表 2021
来自：2021届阅文测试开发...
难度：
29条回答 172100浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号