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

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實現合并兩個排序鏈表的方法詳解就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持武林站長站。