首页 > 试题广场 > 合并两个排序的链表
[编程题]合并两个排序的链表
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

51个回答

添加回答
# merge函数返回的是当前指针的next,当其中一个链表为空,则返回另一个链表
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        # 注意这里要用.val
        if pHead1.val < pHead2.val:
            cur = pHead1
            cur.next = self.Merge(cur.next, pHead2)
        else:
            cur = pHead2
            cur.next = self.Merge(cur.next, pHead1)
        return cur
发表于 2019-05-09 11:42:07 回复(0)
"""
思路:时间复杂度O(n + m),空间复杂度O(1),m和n为两表表长
0.鲁棒性代码,判断是否有空链表。
1.创建虚拟表头,dummy,并用一个p结点记录dummy的位置(p.next = dummy)
2.用两个指针分别指向phead1和pHead2的表头,
  当两个表都没到表末时,比较两个位置值的大小,小的就放到合成链表后,值小的指针向后移
3.如果有一个指针已经到表末了,那么就把另一个表剩余的结点依次加到合成表后。
4.返回真正的链表头,p.next.next
"""
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        
        # pHead1 或 pHead2为空,鲁棒性代码
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        
        #dummy是新合成链表的假表头,p是dummy的前一结点,是为了记录表头而创建的
        #所以p.next.next即为合成的链表的表头结点
        dummy = ListNode(0)
        p = ListNode(0)
        p.next = dummy
        
        #判断两个表中的元素大小,哪个表的值小就把哪个放到合成表后,并指向下一位继续判断
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                dummy.next = pHead1
                dummy = dummy.next
                pHead1 = pHead1.next
            else:
                dummy.next = pHead2
                dummy = dummy.next
                pHead2 = pHead2.next
        
        #两个链表长度不一致,把其中一个表剩余的部分添加到合成表后
        while pHead1:
            dummy.next = pHead1
            dummy = dummy.next
            pHead1 = pHead1.next
        while pHead2:
            dummy.next = pHead2
            dummy = dummy.next
            pHead2 = pHead2.next
        return p.next.next #返回真正的合成表的表头

发表于 2019-04-19 15:54:01 回复(0)
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        node = ListNode(0)
        Head = node
        while pHead1 or pHead2:
            if pHead1 and not pHead2:
                Head.next = pHead1
                pHead1 = pHead1.next
            elif not pHead1 and pHead2:
                Head.next = pHead2
                pHead2 = pHead2.next
            elif pHead1.val <= pHead2.val:
                Head.next = pHead1
                pHead1 = pHead1.next
            else:
                Head.next = pHead2
                pHead2 = pHead2.next
            Head = Head.next
        return node.next

发表于 2019-04-13 21:37:02 回复(0)
python非递归版本:
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        
        
        p=pHead1 if pHead1.val<=pHead2.val else pHead2
        while pHead1 and pHead2:
            if pHead1.val<=pHead2.val:
                t=pHead1.next
                pHead1.next=pHead2
                pHead1=t
            if pHead1!=None:
                if pHead1.val>pHead2.val:
                    l=pHead2.next
                    pHead2.next=pHead1
                    pHead2=l
        return p

发表于 2019-04-01 17:44:00 回复(0)
python
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        pre=newhead=ListNode(0)
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                pre.next=pHead1
                pHead1=pHead1.next
            else:
                pre.next=pHead2
                pHead2=pHead2.next
            pre=pre.next
        if pHead1:
            pre.next=pHead1
        if pHead2:
            pre.next=pHead2
        return newhead.next

发表于 2019-03-22 22:47:30 回复(0)
#使用3个指针,p1,q1,r1表示链表1的相邻三项
#p2,q2表示链表2相邻两项,逐项插入链表1中,注意要判断链表1最后q1是否为空,如果为空,则要停##下来
# -*- 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 pHead2
        if p2 == None:
            return pHead1
        q1 = p1.next
        while p2:
            if q1 == None:
                break
            q2 = p2.next
            r1 = q1.next
            if r1 == None:
                r1_val = float('inf') 
            else:
                r1_val = r1.val
            if p2.val <= q1.val:
                p1.next = p2
                p2.next = q1
                p1 = p2
            if p2.val > q1.val and p2.val <= r1_val:
                q1.next = p2
                p2.next = r1
                p1 = p2
                q1 = r1
            else:
                p1 = q1
                q1 = r1
            p2 = q2
        p1.next = p2
        p2.next = None
        return pHead1
                
发表于 2019-03-19 17:23:54 回复(0)
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        if pHead1==None: return pHead2
        if pHead2==None: return pHead1
        #此时,两条链链头都有元素
        p1,p2=pHead1,pHead2
        #创建一条新链
        pHead,is_equal=ListNode(min(p1.val,p2.val)),p1.val==p2.val
        if is_equal:pHead.next=ListNode(p1.val)
        p=pHead.next if is_equal else pHead
        while p1 and p2:
            #不同情况指针的移动
            if p1.val<p2.val:p1=p1.next
            elif p2.val<p1.val:p2=p2.next
            else:p1,p2=p1.next,p2.next
            #p1或p2到结尾了
            if not p1:
                p.next=p2
                break
            if not p2:
                p.next=p1
                break
            #不等和相等两种情况,插入也有不同
            if not p1.val==p2.val:
                p.next=ListNode(min(p1.val,p2.val))
                p=p.next
            else:
                p.next=ListNode(p1.val)
                p.next.next=ListNode(p1.val)
                p=p.next.next
        return pHead
非递归办法,等会补充一下递归办法
发表于 2019-03-15 16:32:49 回复(0)
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# 思路:p指向L1,q指向L2,比较p,q指向的两个元素,谁小就接入新链表,
# 如果最后有一个链表先结束了,将另一个链表剩余结点全部链入
class Solution:
    # 返回合并后列表
    def Merge(self, L1, L2):
        # write code here
        if L1 is None:
            return L2
        if L2 is None:
            return L1

        p1 = L1
        p2 = L2

        # 构建新链表队头
        L3 = None

        if p1.val < p2.val:
            L3 = L1
            p1 = L1.next
        else:
            L3 = L2
            p2 = L2.next

        # 追踪新链表队尾
        p3 = L3


        while p1 and p2:
            if p1.val < p2.val:
                p3.next = p1
                p1 = p1.next
            else:
                p3.next = p2
                p2 = p2.next
            p3 = p3.next


        # L1终止了,循环链入L2剩余结点
        if p1 is None:
            if p2 is not None:
                p3.next = p2
        # L2终止了,循环链入L1剩余结点
        elif p2 is None:
            if p1 is not None:
                p3.next = p1
        else:
            # 形成队尾
            p3.next = None

        return L3

发表于 2019-03-09 15:16:17 回复(0)
   是不是我对Python的数据结构理解不对啊,为啥每次都出问题啊

 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:
            merge=pHead1
            merge.next=Merge(pHead1.next,pHead2)
        else:
            merge=pHead2
            merge.next=Merge(pHead1, pHead2.next)
        return merge
发表于 2019-03-04 22:59:36 回复(0)
recursive!!!
# -*- coding:utf-8 -*-
# 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:
                head = pHead1
                head.next = self.Merge(pHead1.next, pHead2)
                
            else:
                head = pHead2
                head.next = self.Merge(pHead1, pHead2.next)
            return head
       
发表于 2019-02-12 23:11:38 回复(0)
# -*- 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
        tmp = []
        while True:
            if pHead1.val <= pHead2.val:
                tmp.append(pHead1)
                if pHead1.next == None:
                    while True:
                        tmp.append(pHead2)
                        if pHead2.next == None:
                            break
                        pHead2 = pHead2.next
                    break
                pHead1 = pHead1.next
            else:
                tmp.append(pHead2)
                if pHead2.next == None:
                    while True:
                        tmp.append(pHead1)
                        if pHead1.next == None:
                            break
                        pHead1 = pHead1.next
                    break
                pHead2 = pHead2.next
                
        for i in range(len(tmp)-1):
            tmp[i].next = tmp[i+1]
        tmp[-1].next = None
        return tmp[0]
发表于 2019-01-03 15:27:07 回复(0)
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
        pre = ListNode(0)
        head = pre
        while pHead1 and pHead2:
            if pHead1.val<=pHead2.val:
                pre.next = pHead1
                pHead1 = pHead1.next
            else:
                pre.next = pHead2
                pHead2 = pHead2.next
            pre = pre.next
        if pHead1:
            pre.next = pHead1
        if pHead2:
            pre.next = pHead2
        return head.next

发表于 2018-11-08 15:45:40 回复(0)
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        front1 = pHead1
        front2 = pHead2
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        if pHead1.val >= pHead2.val:
            pHead2.next = self.Merge(pHead1,pHead2.next)
            return front2
        if pHead2.val > pHead1.val:
            pHead1.next = self.Merge(pHead1.next,pHead2)
            return front1
        

发表于 2018-10-22 12:23:06 回复(0)
class Solution:
    def Merge(self, pHead1, pHead2):
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        if pHead1.val <= pHead2.val:
            res = pHead1
            res.next = self.Merge(pHead1.next,pHead2)
        else:
            res = pHead2
            res.next = self.Merge(pHead1,pHead2.next)
        return res
编辑于 2018-10-21 00:15:58 回复(0)
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        a=ListNode(1)
        head=a
        while pHead1 is not None or pHead2 is not None:
            if pHead1 is None:
                a.next= pHead2
                pHead2=None
            elif pHead2 is None:
                a.next= pHead1
                pHead1=None
            elif pHead1.val<=pHead2.val:
                a.next=pHead1
                a=pHead1
                pHead1=pHead1.next
            elif pHead1.val>pHead2.val:
                a.next=pHead2
                a=pHead2
                pHead2=pHead2.next
        return head.next
编辑于 2018-09-21 19:25:56 回复(0)
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        li=ListNode(None)
        first=li
        while pHead1!=None and pHead2!=None:
            if pHead1.val<=pHead2.val:
                li.next=pHead1
                pHead1=pHead1.next
            else:
                li.next=pHead2
                pHead2=pHead2.next
            li=li.next
        if pHead1==None and pHead2!=None:
            li.next=pHead2
        if pHead1!=None and pHead2==None:
            li.next=pHead1
        if pHead1==None and pHead2==None:
            return None
        return first.next
用时23MS

发表于 2018-09-13 16:48:56 回复(0)
Python写法
1. 非递归版本
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

2. 递归版本
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:
            pHead1.next = self.Merge(pHead1.next,pHead2)
            return pHead1
        else:
            pHead2.next = self.Merge(pHead1,pHead2.next)
            return pHead2

编辑于 2018-09-04 16:24:41 回复(0)
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        cur1 = pHead1
        cur2 = pHead2
        while cur1!=None and cur2!=None:
            if cur2.val>=cur1.val:
                tmp1 = cur1.next
                cur1.next = cur2
                tmp2 = cur2.next
                cur2.next = tmp1
                cur1 = tmp1
                cur2 = tmp2
        return pHead1
发表于 2018-08-29 11:10:51 回复(0)

class ListNode:    #注意点:这里可以写出创建节点的类,方便之后的理解

    def __init__(self, val):

        self.val = val

        self.next = None

       

class Solution:

    def Merge(self, pHead1, pHead2):

        #注意点:默认是LishNode作为创建节点类,这里创建1个节点,用连接比较后的较小值节点(0可以换为任意值)

        first = ListNode(0)  

        p = first       #first节点要保存一份,只用备份p节点连接较小值节点

        while pHead1 != None and pHead2 != None:           

            if pHead1.val <= pHead2.val:   #注意点:不能单纯把指向节点的pHead当做是数值,数值是val

                p.next = pHead1        #把小的值连接到p节点

                pHead1 = pHead1.next   #pHead后移一位       

            else:

                p.next = pHead2

                pHead2 = pHead2.next

            p = p.next    #创建的新连接的链表的指针p也要指向最新的节点

           

        #当有一个链表的数值全部遍历完,另一个链表至少剩下1个数值,直接挂在用p连接的链表

        if pHead1 :

            p.next = pHead1

        elif pHead2 :  

            p.next = pHead2

        return first.next      #因为first节点值为0,是自己加的,所以要从后一位节点开始,作为返回值

发表于 2018-08-27 21:30:11 回复(0)
Python 
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 not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        res = ListNode(None)
        if pHead1.val < pHead2.val:
            res = pHead1
            res.next = self.Merge(pHead1.next, pHead2)
        else:
            res = pHead2
            res.next = self.Merge(pHead1, pHead2.next)
        return res

# -*- 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
        res = ListNode(None)
        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
        if pHead1:
            cur.next = pHead1
        if pHead2:
            cur.next = pHead2
        return res.next;

发表于 2018-08-22 19:54:34 回复(0)