python怎么实现合并两个排序的链表

这篇文章主要介绍了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怎么实现合并两个排序的链表”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!