python實(shí)現(xiàn)合并兩個(gè)排序的鏈表

更新時(shí)間：2019年03月03日 11:30:25 作者：goddaniel

這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)合并兩個(gè)排序的鏈表，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

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

題目描述

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

吐槽

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

解題思路

思路1（非遞歸，Low）

找到兩個(gè)鏈表中頭節(jié)點(diǎn)值相對(duì)更小的鏈表，將其作為主鏈表，第二個(gè)鏈表中的元素則不斷加入到主鏈表中。具體策略是：主鏈表定義兩個(gè)指針，指向兩個(gè)相鄰的元素。當(dāng)?shù)诙€(gè)鏈表中的元素值小于主鏈表中第二個(gè)指針時(shí)，將第二個(gè)鏈表的當(dāng)前元素插入到主鏈表兩個(gè)指針指向的元素中間，并調(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

最后給出包含測(cè)試部分的全部代碼：

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

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: