首页 > 试题广场 > 合并两个排序的链表
[编程题]合并两个排序的链表
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
# -*- 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)
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if pHead1 == None or pHead2 == None: return pHead1 or pHead2
        mergedhead = ListNode(None)
        current = mergedhead
        p1, p2 = pHead1, pHead2
        while p1 and p2:
            if p1.val <= p2.val:
                current.next = p1
                p1 = p1.next
            else:
                current.next = p2
                p2 = p2.next
            current = current.next
        current.next = p1 if p1 else p2
        return mergedhead.next
发表于 2019-07-31 00:31:26 回复(0)
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        newp = ListNode(0)
        if pHead1.val <= pHead2.val:
            newp = pHead1
            newp.next = self.Merge(pHead1.next, pHead2)
        else:
            newp = pHead2
            newp.next = self.Merge(pHead1, pHead2.next)
        return newp
            
采用递归的思想,该思想是剑指Offer上的,自行翻看
发表于 2019-07-28 12:06:14 回复(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
        first = ListNode(0)
        p = first
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                p.next = pHead1
                pHead1 = pHead1.next
            else:
                p.next = pHead2
                pHead2 = pHead2.next
            p = p.next
        if pHead1:
            p.next = pHead1
        if pHead2:
            p.next = pHead2
        return first.next
        '''
        p = ListNode(0)
        result = p
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                p.next = pHead1
                pHead1 = pHead1.next
            else:
                p.next = pHead2
                pHead2 = pHead2.next
            p = p.next
        if not pHead1:
            p.next = pHead2
        elif not pHead2:
            p.next = pHead1 
        return result.next
        '''
发表于 2019-07-11 19:49:16 回复(0)
class Solution:
 #返回合并后的列表
    def Merge(self,pHead1,pHead2):
        if pHead1 == None and pHead2 != None:
            return pHead2
        elif pHead1 != None and pHead2 == None:
            return pHead1
        elif pHead1 == None and pHead2 == None:
            return None
        if pHead1.val < pHead2.val:#对头节点进行赋值,因为要返回的是头节点
            head = pHead1
            pHead1 = pHead1.next
        else:
            head = pHead2
            pHead2 = pHead2.next
        cur = head
        while pHead1 != None and pHead2 != None:
            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 head 
我是用非递归的方式写的,可能有点冗余,对于头指针那个地方的代码有些重复🤣🤣🤣
发表于 2019-07-11 16:20:48 回复(0)
#首先设置空链表,然后比较pHead1和pHead2的值大小,将空链表指向它,不断比较,得到最后的结果,注意的是最后此时的链表指针在最后,所以需要找到最初head,而且输出的head.next才是开始的第一个元素#
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        head = p = ListNode(0)
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                p.next = pHead1
                pHead1 = pHead1.next
            else:
                p.next = pHead2
                pHead2 = pHead2.next
            p = p.next
        p.next = pHead1 or pHead2
        return head.next

编辑于 2019-07-10 20:40:00 回复(0)
class Solution:
    # 返回合并后列表,递归的方法
    def Merge(self, pHead1, pHead2):
        if not pHead1:
            return pHead2
        elif not pHead2:
            return pHead1
        
        val1=pHead1.val
        val2=pHead2.val
        if val1<val2:
            p=pHead1
            pnext = self.Merge(pHead1.next,pHead2)
            p.next=pnext
        else:
            p=pHead2
            pnext=self.Merge(pHead1,pHead2.next)
            p.next=pnext
        return p

发表于 2019-07-07 21:51:04 回复(0)
# 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)