合并两个排序的链表_

Python

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

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

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

# -*- 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

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

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号

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号

很粗糙的代码
方法很明确，两个指针，比较小的连在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号

# -*- 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回家

# -*- 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号

新建一个链表，逐个比较大小

# -*- 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

# -*- 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)

合并两个排序的链表

输入

输出

输入

输出

输入

输出

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

问题信息

热门推荐

通过挑战的用户

相关试题