這篇文章主要介紹了python怎么實現合并兩個排序的鏈表，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
題目描述
輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規(guī)則。
解題思路
思路1（非遞歸，Low）
找到兩個鏈表中頭節(jié)點值相對更小的鏈表，將其作為主鏈表，第二個鏈表中的元素則不斷加入到主鏈表中。具體策略是：主鏈表定義兩個指針，指向兩個相鄰的元素。當第二個鏈表中的元素值小于主鏈表中第二個指針時，將第二個鏈表的當前元素插入到主鏈表兩個指針指向的元素中間，并調整指針指向。
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）
網上找到的Java版本，思路如此清晰，以至于用任何額外的文字描述都顯得多余。我用Python重現了思路，代碼如下。哎，美妙的代碼如此的賞心悅目，流連忘返啊…
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 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
感謝你能夠認真閱讀完這篇文章，希望小編分享的“python怎么實現合并兩個排序的鏈表”這篇文章對大家有幫助，同時也希望大家多多支持創(chuàng)新互聯(lián)成都網站設計公司，關注創(chuàng)新互聯(lián)成都網站設計公司行業(yè)資訊頻道，更多相關知識等著你來學習!
另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、網站設計器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
重慶分公司
重慶分公司
