劍指offer：合并兩個排序的鏈表，Python實現(xiàn)

題目描述

輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

吐槽

本來想用遞歸實現(xiàn)，但是大腦卡殼，沒有想到合適的遞歸策略，潛意識里還是把兩個鏈表當(dāng)成兩個數(shù)組來看待，寫出了非遞歸版本的代碼。寫完后回看自己寫的代碼，邏輯不夠一目了然，中間變量過多，代碼過長，一定不是好代碼。上網(wǎng)查閱，發(fā)現(xiàn)一個如此美妙的遞歸版本，哇，寫的好美啊！！！看來我對遞歸的了解和靈活應(yīng)用還不夠啊，至少在鏈表上還不夠啊！！！

解題思路

思路1（非遞歸，Low）

找到兩個鏈表中頭節(jié)點值相對更小的鏈表，將其作為主鏈表，第二個鏈表中的元素則不斷加入到主鏈表中。具體策略是：主鏈表定義兩個指針，指向兩個相鄰的元素。當(dāng)?shù)诙€鏈表中的元素值小于主鏈表中第二個指針時，將第二個鏈表的當(dāng)前元素插入到主鏈表兩個指針指向的元素中間，并調(diào)整指針指向。

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）

網(wǎng)上找到的Java版本，思路如此清晰，以至于用任何額外的文字描述都顯得多余。我用Python重現(xiàn)了思路，代碼如下。哎，美妙的代碼如此的賞心悅目，流連忘返啊…

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