13518219792
这篇文章主要介绍了python怎么实现合并两个排序的链表，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路
思路1（非递归，Low）
找到两个链表中头节点值相对更小的链表，将其作为主链表，第二个链表中的元素则不断加入到主链表中。具体策略是：主链表定义两个指针，指向两个相邻的元素。当第二个链表中的元素值小于主链表中第二个指针时，将第二个链表的当前元素插入到主链表两个指针指向的元素中间，并调整指针指向。
Python代码
def Merge(self, pHead1, pHead2): if not pHead1: return pHead2 if not pHead2: return pHead1 mainHead = pHead1 if pHead1.val <= pHead2.val else pHead2 secHead = pHead2 if mainHead == pHead1 else pHead1 mergeHead = mainHead mainNext = mainHead.next while mainNext and secHead: if secHead.val <= mainNext.val: mainHead.next = secHead secHead = secHead.next mainHead.next.next = mainNext mainHead = mainHead.next else: mainHead = mainNext mainNext = mainNext.next if not mainNext: mainHead.next = secHead return mergeHead
思路2（递归版本，Better）
网上找到的Java版本，思路如此清晰，以至于用任何额外的文字描述都显得多余。我用Python重现了思路，代码如下。哎，美妙的代码如此的赏心悦目，流连忘返啊…
def Merge(self, pHead1, pHead2): 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
最后给出包含测试部分的全部代码：
class Solution: def Merge(self, pHead1, pHead2): 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 def getNewChart(self, list): if list: node = ListNode(list.pop(0)) node.next = self.getNewChart(list) return node class ListNode: def __init__(self, x): self.val = x self.next = None if __name__ == '__main__': list1 = [1, 3, 5] list2 = [0, 1, 4] testList1 = Solution().getNewChart(list1) testList2 = Solution().getNewChart(list2) final = Solution().Merge(testList1, testList2) while final: print(final.val, end=" ") final = final.next
感谢你能够认真阅读完这篇文章，希望小编分享的“python怎么实现合并两个排序的链表”这篇文章对大家有帮助，同时也希望大家多多支持创新互联成都网站设计公司，关注创新互联成都网站设计公司行业资讯频道，更多相关知识等着你来学习!
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、网站设计器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
