首页 > 试题广场 >

合并两个排序的链表

[编程题]合并两个排序的链表
  • 热度指数：1224342 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
Python
Ringo201909111548427头像 Ringo201909111548427
# -*- 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
        p1=pHead1
        p2=pHead2
        if p1==None:
            return p2
        if p2==None:
            return p1
        #初始化p0
        if p1.val<=p2.val:
            p0=p1
            list_head=p1
            p1=p1.next
        else:
            p0=p2
            list_head=p1
            p2=p2.next
        while True:
            if p1==None and p2==None:
                return list_head
            elif p1==None and p2!=None:
                p0.next=p2
                p0=p2
                p2=p2.next
            elif p1!=None and p2==None:
                p0.next=p1
                p0=p1
                p1=p1.next
            else:
                if p1.val<=p2.val:
                    p0.next=p1
                    p0=p1
                    p1=p1.next
                else:
                    p0.next=p2
                    p0=p2
                    p2=p2.next
发表于 2021-07-05 16:03:25 回复(0)
Python
wengJJ头像 wengJJ
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)
Python
食堂在逃干饭王头像 食堂在逃干饭王
和ZhanHeng答案思路一致，写法更加精炼一点的python3版本。 
class Solution:
    def Merge(self, pHead1, pHead2):
        head = ListNode(0)
        temp = head
        while pHead1 != None and pHead2 != None:
            if pHead1.val <= pHead2.val:
                temp.next=pHead1
                pHead1 = pHead1.next
            else:
                temp.next = pHead2
                pHead2 = pHead2.next
            temp = temp.next
            temp.next = None
        if pHead1 != None:
            temp.next = pHead1
        else:
            temp.next = pHead2
        return head.next
        


编辑于 2021-02-09 14:46:15 回复(0)
Python
老和山小学生头像 老和山小学生 
# -*- 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
        TmpNode = ListNode(None)
        NewpHead = TmpNode
        while pHead1&nbs***bsp;pHead2:
            if not pHead1:
                TmpNode.next = pHead2
                break
            elif not pHead2:
                TmpNode.next = pHead1
                break
            elif pHead1.val < pHead2.val:
                TmpNode.next = pHead1
                pHead1 = pHead1.next
            else:
                TmpNode.next = pHead2
                pHead2 = pHead2.next
            TmpNode = TmpNode.next
        return NewpHead.next

编辑于 2020-10-12 09:44:15 回复(0)
Python
anxietyOverFlow头像 anxietyOverFlow 
class Solution:
    def Merge(self, pHead1, pHead2):
        # write code here
        dummy = tail = ListNode(-1)
        while pHead1 or pHead2:
            if not pHead2 or pHead1 and pHead1.val < pHead2.val:
                tail.next = pHead1
                tail = tail.next
                pHead1 = pHead1.next
            else:
                tail.next = pHead2
                tail = tail.next
                pHead2 = pHead2.next
        return dummy.next
只用一个 while 循环
编辑于 2020-09-26 10:44:33 回复(0)
Python
DDooo头像 DDooo 
# -*- 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 pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        if pHead1.val < pHead2.val:
            pHead1.next = self.Merge(pHead1.next, pHead2)
            return pHead1
        else:
            pHead2.next = self.Merge(pHead2.next, pHead1)
            return pHead2
注意：自身调用时，别忘了self.函数名（）
发表于 2020-07-24 11:01:17 回复(0)
Python
sk8_wt头像 sk8_wt 
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:
            start = pHead1
            chan1 = pHead1.next
            chan2 = pHead2
        else:
            start = pHead2
            chan1 = pHead2.next
            chan2 = pHead1
        if not chan1:
            start.next = chan2
            return start
        if not chan2:
            start.next = chan1
            return start
        
        while 1:
            if chan1.val<=chan2.val:
                start.next = chan1
                start = chan1
                chan1 = chan1.next
            else:
                start.next = chan2
                start = chan2
                chan2 = chan2.next
            if not chan1:
                start.next = chan2
                break
            if not chan2:
                start.next = chan1
                break
        return pHead1

发表于 2020-07-17 23:36:44 回复(0)
Python
毛毛虫5755头像 毛毛虫5755 
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        headNode = ListNode(0)
        head = headNode
        while pHead1 != None and pHead2 != None:
            if pHead1.val <= pHead2.val:
                head.next = pHead1
                head = head.next
                pHead1 = pHead1.next
            else:
                head.next = pHead2
                head = head.next
                pHead2 = pHead2.next
        if pHead1 == None:
            head.next = pHead2
        else:
            head.next = pHead1
        
        return headNode.next

发表于 2020-06-04 11:08:46 回复(0)
Python
牛客447097232号头像 牛客447097232号 
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def Merge(self, pHead1, pHead2):
        if pHead1 == None :
            return pHead2
        elif pHead2 == None:
            return  pHead1
        else:
            if pHead1.val < pHead2.val:
                res = pHead1
                pHead1 = pHead1.next
            else:
                res = pHead2
                pHead2 = pHead2.next
            res2 = res
            while(pHead1 != None and pHead2!=None):
                if pHead1.val < pHead2.val:
                    res.next = pHead1
                    res = res.next
                    pHead1 = pHead1.next
                else:
                    res.next = pHead2
                    res = res.next
                    pHead2 = pHead2.next


            if pHead1 != None:
                res.next = pHead1
            else:
                res.next = pHead2
            return res2



s = Solution()
p1 = ListNode(1)
p1.next = ListNode(3)
p1.next.next = ListNode(5)

p2 = ListNode(2)
p2.next = ListNode(4)
p2.next.next = ListNode(6)
ans = s.Merge(p1,p2)
发表于 2020-02-27 01:43:26 回复(0)
Python
牛客108916715号头像 牛客108916715号 
很粗糙的代码
方法很明确，两个指针，比较小的连在head后面，指针后移
直到其中一个到头，再把剩下的连在后面
class Solution:
    def Merge(self, pHead1, pHead2):
        if not pHead1:return pHead2
        if not pHead2:return pHead1
        if not pHead1 and pHead2:return
        i, j ,head= pHead1, pHead2,ListNode(0)
        while i and j:
            if i.val<j.val:
                head.next=i
                head=head.next
                i=i.next
            else:
                head.next = j
                head = head.next
                j = j.next
        if not i and j:
            head.next=j
        elif not j and i:
            head.next=i
        if pHead1.val<pHead2.val:return pHead1
        else:return pHead2

发表于 2020-01-11 13:50:09 回复(0)
Python
吕营头像 吕营
Python Solution: 
# -*- 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
        #初始化
        tmp = ListNode(0)
        pHead = tmp        
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                tmp.next = pHead1
                pHead1 = pHead1.next
            else:
                tmp.next = pHead2
                pHead2 = pHead2.next
            tmp = tmp.next
        if not pHead1:
            tmp.next = pHead2
        if not pHead2:
            tmp.next = pHead1
        return pHead.next


发表于 2019-12-07 14:26:18 回复(0)
Python
牛客465985542号头像 牛客465985542号 
# -*- 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 pHead1 == None and pHead2 == None:
            return None
        elif pHead1 == None:
            return pHead2
        elif pHead2 == None:
            return pHead1
                #创建指针p与q
        p = pHead1
        q = pHead2
        #创建两个指针同时指向新节点
        h = newhead = ListNode(None)
        #两个链表都有元素时
        while p and q:
            #比较节点值得大小，确定先后顺序
            if p.val <= q.val:
                h.next = p
                p = p.next
            else:
                h.next = q
                q = q.next
            #始终h指向最后
            h = h.next
        if p:
            h.next = p
        if q:
            h.next = q
        #用另一个指向返回值
        return newhead.next

发表于 2019-12-05 14:15:58 回复(0)
Python
天山剑客头像 天山剑客 
# -*- 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 pHead1 is None:
                return pHead2
        if pHead2 is None:
                return pHead1
        
        if pHead1.val < pHead2.val:
                pHead = ListNode(pHead1.val)
                pHead1 = pHead1.next
        else:
                pHead = ListNode(pHead2.val)
                pHead2 = pHead2.next
        pLast = pHead
        while pHead1 is not None and pHead2 is not None:
                if pHead1.val < pHead2.val:
                        pNode = ListNode(pHead1.val)
                        pHead1 = pHead1.next
                else:
                        pNode = ListNode(pHead2.val)
                        pHead2 = pHead2.next
                pLast.next =pNode
                pLast = pLast.next
                
        while pHead1 is not None:
                pNode = ListNode(pHead1.val)
                pHead1 = pHead1.next
                pLast.next =pNode
                pLast = pLast.next
                
        while pHead2 is not None:
                pNode = ListNode(pHead2.val)
                pHead2 = pHead2.next
                pLast.next =pNode
                pLast = pLast.next
        
        return pHead
                        

发表于 2019-12-01 13:27:16 回复(0)
Python
黄沙遮天头像 黄沙遮天 
class ListNode:
        def __init__(self,x):
            self.val=x
            self.next=None
class Solution:
    # 返回合并后列表
        def Merge(self, pHead1, pHead2):
        # write code here
           if pHead1==None:
              return pHead2
           elif pHead2==None:
              return pHead1
           else:
              cur1=pHead1
              cur2=pHead2
              if cur1.val<=cur2.val:
                while(cur2):
                    if cur1.next==None:
                        break
                    if cur1.val<=cur2.val and (cur1.next).val>=cur2.val:
                        temp=cur2
                        cur2=cur2.next
                        temp.next=cur1.next
                        cur1.next=temp
                        cur1=cur1.next
                    else:
                        cur1=cur1.next
                if cur1.next==None and cur2!=None:
                    while(cur2):
                        cur1.next=cur2
                        cur2=cur2.next
                        cur1=cur1.next
                return pHead1
              if cur1.val>=cur2.val:
                while(cur1):
                    if cur2.next==None:
                        break
                    if cur2.val<=cur1.val and (cur2.next).val>=cur1.val:
                        temp=cur1
                        cur1=cur1.next
                        temp.next=cur2.next
                        cur2.next=temp
                        cur2=cur2.next
                    else:
                        cur2=cur2.next
                if cur2.next==None and cur1!=None:
                    while(cur1):
                        cur2.next=cur1
                        cur1=cur1.next
                        cur2=cur2.next
                return pHead2
作为一个渣渣，我写的方法比较繁琐。不过思路简单，就是先比较两个链表中的第一个谁比较小，然后以此为最终链表，将另一个链表中的元素
添加进去，但是需要注意的是next为None的情况，因为此时可能发生跳出问题

发表于 2019-11-05 22:10:32 回复(1)
Python
爱吃面包和酸奶的螺丝头像 爱吃面包和酸奶的螺丝

解题思路

数据结构：链表, 时间复杂度：o（n），空间复杂度：o（1）

首先分析合并两个链表的头节点开始。如果链表1的头节点的值小于链表2的头节点，那么链表1的头节点将是合并后链表的头节点。继续合并两个链表中剩余的节点。在两个链表中剩下的节点依然是排序的，因此合并这两个链表的步骤和前面的步骤是一样的。这就是典型的递归过程，我们可以定义递归函数完成这一合并过程。

图片说明 

# -*- 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 pHead1 is None:
            return pHead2
        elif pHead2 is None:
            return pHead1
        pHead = None
        if pHead1.val <= pHead2.val:
            pHead = pHead1
            pHead.next = self.Merge(pHead1.next, pHead2)
        else:
            pHead = pHead2
            pHead.next = self.Merge(pHead1, pHead2.next)
        return pHead
编辑于 2019-10-26 08:56:52 回复(0)
Python
秋水中的鱼头像 秋水中的鱼
非递归版本:造个头节点,一个一个按顺序放到后面 
# -*- 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
        head=ListNode(0)
        node=head
        p1=pHead1
        p2=pHead2
        while p1 or p2:
            if not p1:
                node.next=p2
                break
            if not p2:
                node.next=p1
                break
            if p1.val<=p2.val:
                node.next=p1
                node=node.next
                p1=p1.next
            else:
                node.next=p2
                node=node.next
                p2=p2.next
        return head.next

递归版本代码简单一点 
# -*- 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:
            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


编辑于 2019-10-22 13:00:34 回复(0)
Python
总有几个刁民想要害朕头像 总有几个刁民想要害朕 
# -*- 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 pHead1 == None:
            return pHead2
        if pHead2 == None:
            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
Hint:
递归思想，循环调用Merge函数
发表于 2019-10-10 11:11:54 回复(0)
Python
我要扛offer回家头像 我要扛offer回家 
# -*- 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
        p=ListNode(0)
        res=p
        while pHead1 and pHead2:
            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:
            p.next=pHead1
        elif pHead2:
            p.next=pHead2
        return res.next

发表于 2019-10-03 11:57:25 回复(0)
Python
牛客491657396号头像 牛客491657396号
新建一个链表，逐个比较大小 
# -*- 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
        Node_1=pHead1
        Node_2=pHead2
        HeadNode_=Node_M=ListNode(0)
        while(Node_1 and Node_2):
            if Node_1.val<Node_2.val:
                Node_M.next=Node_1
                Node_1=Node_1.next
            else:
                Node_M.next=Node_2
                Node_2=Node_2.next
            Node_M=Node_M.next
        if Node_1!=None and Node_2==None:
            Node_M.next=Node_1
        if Node_2!=None and Node_1==None:
            Node_M.next=Node_2
        return HeadNode_.next

编辑于 2019-09-04 17:45:55 回复(0)
Python
随心而动_hello_world头像 随心而动_hello_world 
# -*- 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
        # # 方法1：可以指定一个原有的元素作为起点
        # if pHead1.val > pHead2.val:
        #     root = ListNode(pHead2.val)
        #     pHead2 = pHead2.next
        # else:
        #     root = ListNode(pHead1.val)
        #     pHead1 = pHead1.next
        
        # 方法2：任意指定一个元素，下一个节点才是开始
        ans = root = ListNode(100)
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                root.next = ListNode(pHead1.val)
                pHead1 = pHead1.next
            else:
                root.next = ListNode(pHead2.val)
                pHead2 = pHead2.next
            root = root.next

        if pHead1:
            root.next = pHead1
        if pHead2:
            root.next = pHead2

        return ans.next

发表于 2019-08-15 09:31:17 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

合并两个排序的链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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