本文共 2051 字，大约阅读时间需要 6 分钟。

题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

链表：

线性表的链式表示，不需要使用地址连续的存志单元，即不要求逻辑上相邻的元素在物理位置上也相邻。

基本结构：

单链表：每个链表的结点除了存放元素自身的信息，还需要存放一个指向后继的指针。data存放数据，next存放后继结点的地址。

双链表：在单链表的基础上，在数据前存放前任结点的地址。

优缺点：

优点：插入和删除不需要移动其余元素，只需要修改前一个元素的指针；

缺点：失去线性表随机存取的有点，即不能直接找到表中某个特定的结点，只能从头遍历，依次查找。（不能用二分查找）

求解题目：

根据给出的头部文件，可以发现，链表中的每一个结点ListNode都有两个属性，分别存储数据val和下一个结点next。

# -*- coding:utf-8 -*-# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    # 返回合并后列表    def Merge(self, pHead1, pHead2):        # write code here

对于题目的求解思路还是比较简单的，只需要分别判断两个链表中当前元素，将较小的存储到新的链表中。

难点在于在python中链表的表示：使用第一个结点即可表示整个链表，不需要重新创建列表这种...当时我也是卡在这个地方，不知道如何表示了。

# -*- coding:utf-8 -*-# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    # 返回合并后列表    def Merge(self, pHead1, pHead2):        # write code here        pHead = ListNode(0)        #存储最终输出的结点的头部        tem = pHead        while pHead1 and pHead2:            if pHead1.val > pHead2.val:                pHead.next = pHead2                pHead2 = pHead2.next            else:                pHead.next = pHead1                pHead1 = pHead1.next            pHead = pHead.next        #只剩最后一个元素的时候，就不需要在做值的比较了        if pHead1:            pHead.next = pHead1        elif pHead2:            pHead.next = pHead2        return tem.next

在讨论区翻到了用递归思想求解这个问题的算法，觉得还蛮有意思的。

# -*- coding:utf-8 -*-# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    # 返回合并后列表    def Merge(self, pHead1, pHead2):        # write code here        if not pHead1:            return pHead2        elif not pHead2:            return pHead1        else:            if pHead1.val > pHead2.val:                #此时可以确定pHead2是第一个结点，但是要更新pHead2.next                pHead2.next = self.Merge(pHead1, pHead2.next)                return pHead2            else:                #此时可以确定pHead1是第一个结点，但是要更新pHead1.next                pHead1.next = self.Merge(pHead1.next, pHead2)                return pHead1

转载地址：https://blog.csdn.net/sinat_42437278/article/details/117384404 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！