首页 > 试题广场 >

合并两个排序的链表

[编程题]合并两个排序的链表

热度指数：1193806 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $0 \le n \le 1000$ ， $-1000 \le 节点值 \le 1000$
要求：空间复杂度 $O(1)$ ，时间复杂度 $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}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

Java

翼同学

参考代码（Java版本）

迭代

public ListNode Merge (ListNode pHead1, ListNode pHead2) {
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    while (pHead1 != null && pHead2 != null) {
        if (pHead1.val <= pHead2.val) {
            cur.next = pHead1;
            pHead1 = pHead1.next;
        } else {
            cur.next = pHead2;
            pHead2 = pHead2.next;
        }
        cur = cur.next;
    }
    if (pHead1 != null) {
        cur.next = pHead1;
    }
    if (pHead2 != null) {
        cur.next = pHead2;
    }
    return dummy.next;
}

递归

public ListNode Merge(ListNode pHead1, ListNode pHead2) {
    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;
    }
}

发表于 2024-03-10 19:12:03 回复(0)

Java

是你的岚朋友呀

public ListNode Merge (ListNode pHead1, ListNode pHead2) {
    // write code here
    ListNode list = new ListNode(0); //定义一个头节点
    ListNode p = list; //工作指针
    //遍历链表pHead1和pHead2，让节点值更小的节点挂到list上
    while(pHead1 != null && pHead2 != null){
        if(pHead1.val <= pHead2.val){
            p.next = pHead1;
            pHead1 = pHead1.next;
        }else{
            p.next = pHead2;
            pHead2 = pHead2.next;
        }
        p = p.next;
    }
    //让还没有遍历完的节点继续遍历挂到list上
    while(pHead1 != null){
        p.next = pHead1;
        pHead1 = pHead1.next;
        p = p.next;
    }
    while(pHead2 != null){
        p.next = pHead2;
        pHead2 = pHead2.next;
        p = p.next;
    }
    return list.next;
}

时间复杂度O(m+n),空间复杂度O(1)

发表于 2024-03-02 16:25:15 回复(0)

Java

牛客119190309号

public ListNode Merge (ListNode pHead1, ListNode pHead2) {

// write code here

List<Integer> list= new ArrayList<>();

while(pHead1 != null){

list.add(pHead1.val);

pHead1 = pHead1.next;

}

while(pHead2 != null){

list.add(pHead2.val);

pHead2 = pHead2.next;

}

//核心语法

Collections.sort(list, new Comparator<Integer>(){

public int compare(Integer a,Integer b){

return a>b?1:a==b?0:-1;

}

});

ListNode temp= null;

ListNode res = null;

for(int i=0;i<list.size();i++){

int num = list.get(i);

ListNode node = new ListNode(num);

if(i == 0){

temp = node;

res = temp;

}else{

temp.next = node;

temp = node;

}

return res;

}

吐槽一下，在线编程不能用jdk8的lambda表达式，感觉不爽

发表于 2024-02-28 21:52:37 回复(1)

Java

2320710106江锦华

可运行

public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;

        ListNode head = new ListNode(0);
        ListNode cur = head;

        for (; list1 != null && list2 != null; cur = cur.next) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
        }

        if (list1 != null)
            cur.next = list1;
        else
            cur.next = list2;

        ListNode res = head.next;
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }
        System.out.println();

        return head.next;
    }
}

编辑于 2024-01-30 14:12:19 回复(0)

Java

不要卷我了

while里面套两个while，有点像快排的结构

public class Solution {
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        if(pHead1==null || pHead2==null) // 含空表的情况
            return (pHead1==null)? pHead2:pHead1;

        ListNode head = (pHead1.val >= pHead2.val)?pHead2:pHead1; // 注意是>=
        ListNode p1 = pHead1, p2 = pHead2, pre1, pre2; // pre1为p1前驱，pre2同理
        while(p1!=null && p2!=null){
            if(p1.val>=p2.val){ // 两个>=是一致的
                pre2 = p2;
                while(p2!=null && p1.val>=p2.val){ // 当甲链表大于乙链表当前节点时
                    pre2 = p2;
                    p2 = p2.next;
                }
                pre2.next = p1; // 当乙链表出现第一个大于甲链表当前节点时
            }else{
                pre1 = p1;
                while(p1!=null && p2.val>p1.val){ // 否则甲往后
                    pre1 = p1;
                    p1 = p1.next;
                }
                pre1.next = p2;
            }  
        }
        return head;
    }
}

发表于 2024-01-02 17:03:36 回复(0)

Java

热血的卡尔在求佛

public ListNode Merge (ListNode pHead1, ListNode pHead2) {

// write code here

ListNode dommy = new ListNode(0);

ListNode aa = dommy;

while (pHead1 != null && pHead2 != null){

ListNode first = null;

ListNode two = null;

if(pHead1.val < pHead2.val){

first = pHead1.next;

two = pHead2;

aa.next = pHead1;

aa.next.next = null;

aa = aa.next;

}else if(pHead1.val == pHead2.val){

first = pHead1.next;

two = pHead2.next;

aa.next = pHead1;

aa.next.next = null;

aa.next.next = pHead2;

aa.next.next.next = null;

aa = aa.next.next;

}else {

first = pHead1;

two = pHead2.next;

aa.next = pHead2;

aa.next.next = null;

aa = aa.next;

}

pHead1 = first;

pHead2 = two;

}

if(pHead1 != null){

aa.next = pHead1;

}

if(pHead2 != null){

aa.next = pHead2;

}

return dommy.next;

}

编辑于 2023-12-12 17:52:45 回复(0)

Java

-Panda君-

import java.util.*;

public class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}
/

public class Solution {

/**

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

 *

 *

@param pHead1 ListNode类
@param pHead2 ListNode类

@return ListNode类

public ListNode Merge (ListNode pHead1, ListNode pHead2) {

  // write code here

  ListNode dump = new ListNode(-1); // 用于返回

  ListNode pre = dump;

  if(pHead1 == null&&pHead2==null){

      return null;

  }

  if(pHead1 == null&&pHead2!=null){

      return pHead2;

  }

   if(pHead1 != null&&pHead2==null){

      return pHead1;

  }

  while(pHead1!=null&&pHead2!=null){

      if(pHead1.valpHead2.val){

          pre.next = pHead1;

          pre = pHead1;

          pHead1 = pHead1.next;

      }else{

          pre.next = pHead2;

          pre = pHead2;

          pHead2 = pHead2.next;

      }

  }

  if(pHead1 == null){

      pre.next = pHead2;

  }

  if(pHead2 == null){

       pre.next = pHead1;

  }

  return dump.next;

}

发表于 2023-12-02 19:10:25 回复(0)

Java

Lengxf_

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null) return pHead2;
        if (pHead2 == null) return pHead1;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val > pHead2.val) {
                cur.next = pHead2;
                pHead2 = pHead2.next;
            } else {
                cur.next = pHead1;
                pHead1 = pHead1.next;
            }
            cur = cur.next;
        }
        if (pHead1 != null) {
            cur.next = pHead1;
        }

        if(pHead2 != null){
            cur.next = pHead2;
        }

        return dummy.next;
    }
}

发表于 2023-11-15 16:16:09 回复(0)

Java

王总统治世界

// 简单易懂，双指针比较大小
public class Solution {

    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // 最后返回的链表
        ListNode pre = new ListNode(-1);
        // 操作指针
        ListNode curPre = pre;
        
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;

        // 遍历比较大小，小的连接上
        while(cur1 != null && cur2 != null ){
            if(cur1.val < cur2.val){
                curPre.next = cur1;
                cur1 = cur1.next;
            }else{
                curPre.next = cur2;
                cur2 = cur2.next;
            }
            curPre = curPre.next;
        }

        // 把剩余的链接上
        if(cur1 != null){
            curPre.next = cur1;
        }
        if(cur2 != null){
            curPre.next = cur2;
        }
        
        return pre.next;
    }
}

发表于 2023-09-25 22:50:27 回复(0)

Java

练习时长两年半的太平湖水怪很理智

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        // 新链表的虚拟头节点
        ListNode dummy = new ListNode(0);
        // 当前节点
        ListNode cur = dummy;
        // 链表1
        ListNode pre1 = pHead1;
        // 链表2
        ListNode pre2 = pHead2;
        while (pre1 != null && pre2 != null) {
            // 表1头节点的值<=表2头节点的值
            if (pre1.val <= pre2.val) {
                // 将表1的头节点拼接到新表末尾
                cur.next = pre1;
                // 删除表1的头节点，即头结点后移一位
                pre1 = pre1.next;
            // 表2头节点的值>表2头节点的值时，对表2进行与表1同样的操作
            } else {
                cur.next = pre2;
                pre2 = pre2.next;
            }
            // dummy表的当前节点（即末尾节点）后移一位
            cur = cur.next;            
        }
        // 表1表2其中一个完成所有节点拼接到dummy表后，表1表2中有一个还有剩余元素，此时将剩余节点拼接到dummy表中
        cur.next = pre1 != null ? pre1 : pre2;
        // 返回dummy所指向的节点
        return dummy.next;
    }
}

发表于 2023-09-22 15:28:27 回复(0)

Java

夹仲见歌

public class Solution {
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        if(pHead1==null)return pHead2;
        if(pHead2==null)return pHead1;
        if(pHead1==null && pHead2==null)return null;
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        ListNode p1 = pHead1, p2 = pHead2;
        while(p1!=null && p2!=null){
            if (p1.val > p2.val){
                head.next = p2;
                p2 = p2.next;
            }
            else{
                head.next = p1;
                p1 = p1.next;
            }
            head = head.next;
        }
        if(p1!=null)
            head.next = p1;
        if(p2!=null)
            head.next = p2;
        return dummy.next;
    }
}

发表于 2023-09-16 20:19:05 回复(0)

Java

LQY_

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param pHead1 ListNode类

* @param pHead2 ListNode类

* @return ListNode类

public ListNode Merge (ListNode pHead1, ListNode pHead2) {

// write code here

ListNode head, headPointer = new ListNode(0), currentNext1 = pHead1, currentNext2 = pHead2;

if(pHead1 == null){

return pHead2;

}

if(pHead2 == null){

return pHead1;

}

if(pHead1.val < pHead2.val){

head = pHead1;

headPointer.next = head;

currentNext1 = currentNext1.next;

}

else{

head = pHead2;

headPointer.next = head;

currentNext2 = currentNext2.next;

}

while(currentNext1 != null && currentNext2 != null){

if(currentNext1.val < currentNext2.val){

head.next = currentNext1;

head = head.next;

currentNext1 = currentNext1.next;

}

else{

head.next = currentNext2;

head = head.next;

currentNext2 = currentNext2.next;

}

if(currentNext1 == null){

head.next = currentNext2;

}

else{

head.next = currentNext1;

}

return headPointer.next;

}

发表于 2023-09-14 18:30:32 回复(0)

Java

StephenCurryMVP

public ListNode Merge (ListNode pHead1, ListNode pHead2) {

if(pHead1 == null) return pHead2;

if(pHead2 == null) return pHead1;

ListNode L;

if(pHead1.val >= pHead2.val){

L = pHead2;

pHead2 = pHead2.next;

}

else{

L = pHead1;

pHead1 = pHead1.next;

}

ListNode r = L;

while(pHead1 != null && pHead2 != null){

if(pHead1.val >= pHead2.val){

r.next = pHead2;

r = pHead2;

pHead2 = pHead2.next;

}

else{

r.next = pHead1;

r = pHead1;

pHead1 = pHead1.next;

}

if(pHead1 != null){

r.next = pHead1;

}

if(pHead2 != null){

r.next = pHead2;

}

return L;

}

发表于 2023-08-21 23:45:06 回复(0)

Java

要讲武德🖐🏻

public ListNode Merge (ListNode pHead1, ListNode pHead2) {

// write code here

ListNode dummy = new ListNode(-1);

ListNode cur = dummy;

while(pHead1 != null && pHead2 != null){

if(pHead1.val <= pHead2.val){

cur.next = new ListNode(pHead1.val);

pHead1 = pHead1.next;

}else if(pHead1.val > pHead2.val){

cur.next =new ListNode(pHead2.val);

pHead2 = pHead2.next;

}

cur = cur.next;

}

if(pHead1 == null){

cur.next = pHead2;

}else if(pHead2 == null){

cur.next = pHead1;

}

return dummy.next;

}

发表于 2023-08-10 16:07:41 回复(0)

Java

牛客101757813号

public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        if(pHead1 == null){
            return pHead2;
        }
        if(pHead2 == null){
            return pHead1;
        }
        ListNode result = new ListNode(0);
        ListNode nextNode = new ListNode(0);
        result.next = nextNode;
        while(pHead1 != null && pHead2 != null){
            if(pHead1.val > pHead2.val){
                nextNode.val = pHead2.val;
                pHead2 = pHead2.next;
                if(pHead2 != null){
                    nextNode.next = new ListNode(0);
                    nextNode = nextNode.next;
                }
            }else{
                nextNode.val = pHead1.val;
                pHead1 = pHead1.next;
                if(pHead1 != null){
                    nextNode.next = new ListNode(0);
                    nextNode = nextNode.next;
                }
            }
        }
        if(pHead1 != null){
            nextNode.next = pHead1;
        }else{
            nextNode.next = pHead2;
        }
        return result.next;
    }

发表于 2023-08-02 21:00:24 回复(0)

Java

joyboysimba

public class Solution {
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        if (pHead1 == null) return pHead2;
        else if (pHead2 == null) return pHead1;
        else {
            ListNode newhead;
            if (pHead1.val < pHead2.val) {newhead = pHead1;pHead1=pHead1.next;}
            else {newhead = pHead2;pHead2=pHead2.next;}
            ListNode p = newhead;
            while (pHead1 != null && pHead2 != null) {
                if (pHead1.val < pHead2.val) {
                    p.next = pHead1;
                    p = p.next;
                    pHead1 = pHead1.next;
                } else {
                    p.next = pHead2;
                    p = p.next;
                    pHead2 = pHead2.next;
                }
            }
            if(pHead1==null) p.next=pHead2;
            else p.next=pHead1;
            return newhead;
        }
    }
}

思路：首先判断特殊情况（为空时），定义一个newhead=初始值最小的那个，然后h1或者h2向后移位，每次比较h1和h2的大小，谁小就连谁。最后当有一个连完了，直接把另一个整个接上就行。

发表于 2023-07-18 21:56:32 回复(0)

Java

做则必成的勇气和信心

public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // 比较两个链表的值（每个链表各自已经是升序的）
       
        ListNode dummy=new ListNode(-1);
        ListNode head=dummy;
        while(pHead1!=null&&pHead2!=null){
            if(pHead1.val<=pHead2.val){
                head.next=pHead1;
                pHead1=pHead1.next;
                head=head.next;
            }else{
                head.next=pHead2;
                pHead2=pHead2.next;
                head=head.next;
            }
        }
        while(pHead1!=null){
            head.next=pHead1;
            pHead1=pHead1.next;
            head=head.next;
        }
        while(pHead2!=null){
            head.next=pHead2;
            pHead2=pHead2.next;
            head=head.next;
        }
        return dummy.next;
    }

发表于 2023-07-16 10:24:58 回复(0)

Java

牛客710670511号

比较简单

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2)  {
        ListNode reNode = new ListNode(-1);
        ListNode re2 = reNode;
       
        while (pHead1 != null || pHead2 != null) {
            if (pHead2 == null || pHead1 != null && pHead1.val <= pHead2.val) {
                re2.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                re2.next = pHead2;
                pHead2 = pHead2.next;
            }
            re2 = re2.next;
        }
        return reNode.next;
    }
}

发表于 2023-06-18 22:04:06 回复(0)

提交观点

问题信息

链表 2021

来自：2021届阅文测试开发...

难度：

281条回答 3155收藏 172064浏览

通过挑战的用户

查看代码

北小城

2023-03-13 14:10:52
胖布布

2023-03-04 15:23:45
牛客84631...

2023-02-09 10:14:52
牛客48257...

2023-01-31 10:20:36
饭否啊

2022-12-27 08:33:29

合并两个排序的链表

输入

输出

输入

输出

输入

输出

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

参考代码（Java版本）

迭代

递归

问题信息

热门推荐

通过挑战的用户

相关试题