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

Python  /  管理员 发布于 7年前   318

剑指offer：合并两个排序的链表，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 nodeclass ListNode: def __init__(self, x):  self.val = x  self.next = Noneif __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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。