怎么使用python實現合并兩個排序鏈表

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

輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。

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

附注：

遞歸算法運行邏輯看著復雜,但是形式上都是簡單的.每一層都表達了”當前結點要做的任務”.

思考遞歸算法的步驟應該是

1) 明確每一層要做的任務,eg,選擇鏈表中較小值作為當前結點

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

3) 明確return條件,eg,當p1,p2其中有一個為空時,遞歸任務結束

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

這也是函數式編程的魅力所在.

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