怎么使用python實現(xiàn)合并兩個排序鏈表

這篇文章主要介紹了怎么使用python實現(xiàn)合并兩個排序鏈表，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

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

1、迭代方法

  def Merge(self, pHead1, pHead2):
    p1, p2 = pHead1, pHead2
    if p1 and p2:
      if p1.val < p2.val:
        head = p1
        p1 = p1.next
      else:
        head = p2
        p2 = p2.next
      cur = head
    elif p1:
      return p1
    else:
      return p2

    while p1 and p2:
      if p1.val < p2.val:
        cur.next = p1
        p1 = p1.next
      else:
        cur.next = p2
        p2 = p2.next
      cur = cur.next
    if p1:
      cur.next = p1
    else:
      cur.next = p2
    return head

2、遞歸方法

  def Merge_rcv(self, pHead1, pHead2):
    if not pHead1:
      return pHead2
    if not pHead2:
      return pHead1
    if pHead1.val < pHead2.val:
      pres = pHead1
      pres.next = self.Merge(pHead1.next, pHead2)
    else:
      pres = pHead2
      pres.next = self.Merge(pHead1, pHead2.next)
    return pres

附注：

遞歸算法運行邏輯看著復(fù)雜,但是形式上都是簡單的.每一層都表達了”當(dāng)前結(jié)點要做的任務(wù)”.

思考遞歸算法的步驟應(yīng)該是

1) 明確每一層要做的任務(wù),eg,選擇鏈表中較小值作為當(dāng)前結(jié)點

2) 明確每一層的任務(wù)的完結(jié)點和遞歸連接點,eg,在pres.next處進行下一層遞歸

3) 明確return條件,eg,當(dāng)p1,p2其中有一個為空時,遞歸任務(wù)結(jié)束

幾乎所有的遞歸算法都可以沿著這三個要求思考構(gòu)造,很自然不怕寫遞歸算法,三個問題能自己在腦里回答出來,稍加修飾就是一個完整的遞歸算法.

這也是函數(shù)式編程的魅力所在.

感謝你能夠認真閱讀完這篇文章，希望小編分享的“怎么使用python實現(xiàn)合并兩個排序鏈表”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!