首页 > 试题广场 >

合并两个排序的链表

[编程题]合并两个排序的链表
  • 热度指数:1187287 时间限制: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,点此查看相关信息
public ListNode Merge(ListNode list1,ListNode list2) {
         if(list1 != null && list2==null){
            return list1;
        }
        if(list2 != null && list1==null){
            return list2;
        }
        ListNode tail = new ListNode(0);
        ListNode head = tail;

        while(list1 != null && list2 != null){
            if(list1.val > list2.val){
                ListNode node = new ListNode(list2.val);
                tail.next = node;
                tail = tail.next;
                list2 = list2.next;
            }else{
                ListNode node = new ListNode(list1.val);
                tail.next = node;
                tail = tail.next;
                list1 = list1.next;
            }
        }
        while(list1 != null){
            ListNode node = new ListNode(list1.val);
            tail.next = node;
            tail = tail.next;
            list1 = list1.next;
        }
        while (list2 != null){
            ListNode node = new ListNode(list2.val);
            tail.next = node;
            tail = tail.next;
            list2 = list2.next;
        }
        return head.next;
    }一次过,头指针默认为0,返回头指针的下一个,就是合并的结果,
与剑指Offer上不同,这里不是递归实现的。。。。

编辑于 2015-09-19 16:27:56 回复(0)
更多回答
递归版本:
 public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        if(list1.val <= list2.val){
            list1.next = Merge(list1.next, list2);
            return list1;
        }else{
            list2.next = Merge(list1, list2.next);
            return list2;
        }        
    }
非递归版本:
if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode mergeHead = null;
        ListNode current = null;      
        while(list1!=null && list2!=null){
            if(list1.val <= list2.val){
                if(mergeHead == null){
                   mergeHead = current = list1;
                }else{
                   current.next = list1;
                   current = current.next;
                }
                list1 = list1.next;
            }else{
                if(mergeHead == null){
                   mergeHead = current = list2;
                }else{
                   current.next = list2;
                   current = current.next;
                }
                list2 = list2.next;
            }
        }
        if(list1 == null){
            current.next = list2;
        }else{
            current.next = list1;
        }
        return mergeHead;

发表于 2016-07-20 22:26:55 回复(97)
// 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
    if(pHead1 == null && pHead2 == null) return null
    let res = {
        val: null,
        next:null,
    }
    let cur = res
    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
    else if(pHead2 != null) cur.next = pHead2
    return res.next
    
}
module.exports = {
    Merge : Merge
};

发表于 2022-08-04 21:45:20 回复(0)
class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # 创建哨兵结点和当前结点
        sen= cur = ListNode(-1)
        # 当两个链表都不为空时候
        while pHead1 and pHead2:
            # 链表1的值更小
            if pHead1.val <= pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            # 链表2的值更小
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            # 当前结点后移
            cur = cur.next
        # 链表1不为空,将剩余的链表1连接至当前结点后
        if pHead1: cur.next = pHead1
        # 链表2不为空,将剩余的链表2连接至当前结点后
        if pHead2: cur.next = pHead2
        return sen.next

发表于 2022-07-19 22:50:21 回复(0)
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = phead;
    if(pHead1 == NULL)
        return pHead2;
    if(pHead2 == NULL)
        return pHead1;
    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 = pHead2;
    }
    if(pHead2 == NULL)
    {
        cur->next = pHead1;
    }
    return phead->next;
}
发表于 2022-05-20 17:50:15 回复(0)
public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode start = new ListNode(0);
        ListNode cur = start;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 == null ? list2 : list1;
        return start.next;
    }
}

发表于 2022-05-07 20:37:29 回复(1)
class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        res = ListNode(0)
        cur = res
        while pHead1 and 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 if pHead1 else pHead2 
        return res.next

发表于 2022-05-05 21:07:37 回复(0)
这个题如果用递归的话,后边的链表长于前边的链表的话,只能按前边的链表长度进行排序了,合并之后的链表后边就不是完全的排序了
发表于 2022-03-16 22:28:06 回复(1)
 public ListNode Merge(ListNode a, ListNode b) {
        //防御阶段 
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }    
        //进攻阶段
        //循环和双指针
        ListNode result = new ListNode(0);
        ListNode pre = result;
        while (a != null && b != null) {
            if(a.val<b.val){
                pre.next=a;
                a = a.next;
            }else{
                pre.next=b;
                b = b.next;
            }
            pre =pre.next;
        }
        if(a!=null){
            pre.next =a;
        }
        if(b!=null){
           pre.next=b; 
        }
        return result.next;
    }

发表于 2022-03-13 13:50:26 回复(0)
Go 解题方法
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
/*思路:
新建一个头节点,然后从两个链表中取出较小值,放置于头节点链表后
*/
    
    var ret = &ListNode{}
    head := ret
    for pHead1!=nil && pHead2!=nil{
        //取出较小的节点
        if pHead1.Val < pHead2.Val{
            ret.Next = pHead1
            pHead1 = pHead1.Next
        }else{
            ret.Next = pHead2
            pHead2 = pHead2.Next
        }
        ret = ret.Next
    }
    //如果某一链表还有数据,则直接添加到ret链表后面
    if pHead1!=nil{
        ret.Next = pHead1
    }
	if pHead2!=nil{
        ret.Next = pHead2
    }
    
    // 头节点无数据,需略过
    return head.Next
}


发表于 2022-01-01 16:34:51 回复(0)

struct ListNode*firstinsert(struct ListNode*pHead1,struct ListNode*pHead2)//从前面插入节点
{
    pHead2->next=pHead1;
    return pHead2;
}
void midinsert(struct ListNode*temp1,struct ListNode*pHead1,struct ListNode*pHead2)//从中间任意位置插入节点
{
    pHead2->next=pHead1;
    temp1->next=pHead2;
}
void lastinsert(struct ListNode*temp1,struct ListNode*pHead2)//从后面插入节点
{
    temp1->next = pHead2;
}
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
     struct ListNode* temp1=pHead1;
    struct ListNode* temp2=pHead2;
    struct ListNode* root=pHead1;
//root记录头节点的地址
    if(pHead1==NULL&&pHead2==NULL)return pHead1;//任意一条链表为空则返回另一条链表
如果两条为空则随便返回一条链表
    else if(pHead1==NULL)
    {
        return pHead2;
    }
    else if(pHead2==NULL)
    {
        return pHead1;
    }
    else{
        while(pHead1!=NULL)//遍历链表1与链表2的节点比较
        {
            if(temp2==NULL)return root;//temp2为空表示比较完返回root
            if(pHead1->val<=pHead2->val)
            {
                temp1=pHead1;
                pHead1=pHead1->next;
            }
            else{
                if(pHead1==root){//如果链表1的节点为头节点则从前面插入节点
否则从中间插入节点
                    temp2=temp2->next;
                    root = firstinsert(pHead1,pHead2);
                    pHead2=temp2;
                    pHead1=root;
                }
                else{
                    temp2=temp2->next;
                    midinsert(temp1,pHead1,pHead2);
                    pHead2=temp2;
                    pHead1=root;
                }
            }
        }
//跳出循环说明现在pHead2后面的节点都大与链表1最大的节点,所以只要从后面插入节点直接返回
        lastinsert(temp1,pHead2);
        //if(pHead2==NULL)
        return root;
        //pHead1=root;
    }
}
发表于 2021-11-28 18:48:02 回复(0)
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)
import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 == null && list2 == null){
            return null;
        }
        if (list1 != null && list2 == null){
            return list1;
        }
        if (list2 != null && list1 == null){
            return list2;
        }
        List<Integer> list = new ArrayList<>();
        while (list1 != null){
            list.add(list1.val);
            list1 = list1.next;
        }
        while (list2 != null){
            list.add(list2.val);
            list2 = list2.next;
        }
        Collections.sort(list);
        ListNode newHead = new ListNode(list.get(0));
        ListNode tempNode = newHead;
        for (int i = 1; i < list.size();i++){
            tempNode.next = new ListNode(list.get(i));
            tempNode = tempNode.next;
        }
        tempNode.next = null;
        return newHead;
    }
}

发表于 2021-11-13 12:16:15 回复(0)
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode ans = new ListNode(0), root = ans;
        ListNode temp1 = list1, temp2 = list2;
        while(temp1 != null && temp2 != null) {
            if(temp1.val < temp2.val) {
                root.next = temp1;
                temp1 = temp1.next;
            } else {
                root.next = temp2;
                temp2 = temp2.next;
            }
            root = root.next;
        }
        root.next = temp1 == null ? temp2 : temp1;
        return ans.next;
    }
}

发表于 2021-09-09 19:18:17 回复(0)
书上经典的归并有序链表
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //新建一个头节点,最后用来返回结果,result就用来固定新链表的头节点
        ListNode result = new ListNode(0);
        //创建临时指针,用来连接节点
        ListNode cur = result;
        //当有一方的节点被连接完毕,则另一个链表剩下的可直接连接在cur尾部。
        while(list1 != null && list2 != null){
            //当list1中的当前节点值小于等于list2中的节点值时,我们连接list1的当前节点。
            if(list1.val <= list2.val){
                //将list1的当前头节点连接在cur尾部。
                cur.next = list1;
                //list1头节点指针后移。
                list1 = list1.next;
                //cur后移,用于连接下一个节点
                cur = cur.next;
            }else{
                //反之,我们连接list2的当前头节点
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }
        //直接将另一个链表剩下的部分连接在cur尾部
        if(list1 != null) cur.next = list1;
        if(list2 != null) cur.next = list2;
        //因为是从cur的next开始连接的,所以返回result的下一个节点。
        return result.next;
    }
}

发表于 2021-08-06 18:08:11 回复(0)
使用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)
Python
为了防止递归算法因为内存问题又炸了,提供了另一种迭代解法,只需要创建一个新的头节点
牛批(newp)串起来即可
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
#         递归
#         if not pHead1 and not pHead2:
#             return None
#         if not pHead1:
#             return pHead2
#         if not pHead2:
#             return pHead1
#         if pHead1.val <= pHead2.val:
#             pHead1.next = self.Merge(pHead1.next,pHead2)
#             return pHead1
#         else:
#             pHead2.next = self.Merge(pHead1,pHead2.next)
#             return pHead2
#         迭代
        if not pHead1 and not pHead2:
            return None
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        newHead = ListNode(-1)
        newp = newHead
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                newp.next = pHead1
                newp = newp.next
                pHead1 = pHead1.next
            else:
                newp.next = pHead2
                newp = newp.next
                pHead2 = pHead2.next
        if not pHead1 and not pHead2:
            return newHead
        if not pHead1:
            newp.next = pHead2
        if not pHead2:
            newp.next = pHead1
        return newHead.next
            


发表于 2021-06-13 00:13:17 回复(0)
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def Merge(self,pHead1,pHead2):
        # 定义一个初值为0的链表作为存储
        # temp始终指向链表的最后一个节点
        temp = ListNode(0)
        # temp会不断后移,所以定义另一个值指向temp头节点
        res = temp
        
        # 终止条件:链表1或者链表2遍历结束,剩下一个链表如果还有节点,直接使用temp.next指向其即可
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                temp.next = pHead1
                pHead1 = pHead1.next
            else:
                temp.next = pHead2
                pHead2 = pHead2.next
            temp = temp.next
            """
            解释一下:链表1和2同时从头节点开始遍历,当链表1头节点的值小于链表2头节点值,temp.next指向链表1头节点,同时链表1头节点和temp向后移动一位
            反之,temp.next指向链表2,链表2头节点和temp向后移动一位
            """
            
        if pHead1:
            temp.next = pHead1
        if pHead2:
            temp.next = pHead2
        
        return res.next
class Solution:
    def Merge(self,pHead1,pHead2):
        # 递归终止条件
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        
        # 开始递归
        # 何为递归?先比较链表1和链表2的头节点值,此处链表1头节点值小,
        # 递归就是默认链表1第二个节点和链表2从头节点开始已经通过Merge合并好
        if pHead1.val <= pHead.val:
            pHead1.next = self.Merge(pHead1.next,pHead2)
            return pHead1
        else:
            pHead2.next = self.Merge(pHead,pHead2.next)
            return pHead2


编辑于 2021-04-09 17:09:19 回复(0)
递归:
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        if pHead1.val < pHead2.val:
            pHead1.next = self.Merge(pHead1.next, pHead2)
            return pHead1
        else:
            pHead2.next = self.Merge(pHead1, pHead2.next)
            return pHead2
迭代:
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        dummy = ListNode(-1)
        cur = dummy
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                cur.next = pHead1
                cur = cur.next
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                cur = cur.next
                pHead2 = pHead2.next
        cur.next = pHead1 if pHead1 else pHead2
        return dummy.next



发表于 2021-02-18 10:05:21 回复(0)
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head=new ListNode(0),node=head;
        while(list1!=null&&list2!=null){
            if(list2.val<list1.val){
                node.next=list2;
                list2=list2.next;
            }else{
                node.next=list1;
                list1=list1.next;
            }
            node=node.next;
        }
        node.next=(list1!=null?list1:list2);
        return head.next;
    }
}

发表于 2020-12-31 16:16:59 回复(0)
具体处理类似于归并排序中的数组合并
    /**
    题目描述
    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
    */
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode newHead = new ListNode(-1), end = newHead;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                end.next = list1;
                end = end.next;
                list1 = list1.next;
            }else {
                end.next = list2;
                end = end.next;
                list2 = list2.next;
            }
        }
        if (list1 != null) {
            end.next = list1;
        }
        if (list2 != null) {
            end.next = list2;
        }
        return newHead.next;
    }


发表于 2020-10-04 16:40:20 回复(0)