題目描述
輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則，解題思路分析：
這兩個鏈表都是單調遞增的，合并這兩個鏈表的意思是將這兩個鏈表全部打亂后，再根據從小到大的順序進行重新指向，最后得到一個新的鏈表，我們可以直接使用遞回的方法來做這個題目，代碼如下：
class Solution: # 回傳合并后串列 #這個遞回的方法簡直是無敵啊！ def Merge(self, pHead1, pHead2): #判斷鏈表是否存在，如果不存在就回傳另外一個鏈表，另一個鏈表必定是單調不減的 if not pHead1: return pHead2 if not pHead2: return pHead1 #采用分治的思想？ if pHead1.val < pHead2.val: #已經確定了新鏈表的表頭，那么我們只需要后面的鏈表即可，因此從phead1的第二個元素開始算，重新整合排序 #因為這個函式一定回傳的是一個有序的鏈表的緣故 pHead1.next = self.Merge(pHead1.next, pHead2) return pHead1 else:#pHead1.val > pHead2.val pHead2.next = self.Merge(pHead1, pHead2.next) return pHead2
因為我們Merge函式回傳的一定是一個具有從小到大順序的鏈表，因此我們拿到一個兩組鏈表當中進行走一次比較之后更小的值，直接采用遞回，將更小值所在的鏈表下一個數值帶入進去Merge函式當中進行遞回，這樣就可以直接得到最后的結果了，這種解法很難想到，但多刷一刷題目慢慢就有經驗了，
方法二：
創建一個新的鏈表，然后將得到的這兩個鏈表當中的每一個值進行比較，讓依次在這兩個拿到的鏈表當中比較得到的最小的數放入到這個新的鏈表當中，這個新的鏈表用tmp來表示，但是我們已經得到這個新的鏈表之后，新的鏈表當中的指標已經指向了這個新鏈表的末尾，因此在創建這個新鏈表的同時我們需要引入一個變數pHead來記錄新鏈表tmp表頭的地址，最后直接return這個pHead的next下一個就是我們整個從小到大排列的鏈表了，代碼如下所示：
class Solution: def Merge(self, pHead1, pHead2): #方法二:新建一個鏈表，利用傳統的方法將遍歷后的鏈表注入進入這個新鏈表當中 tmp=ListNode(0) pHead=tmp#首先定義一個臨時變數pHead，代表了tmp的指標 while pHead1 and pHead2: if pHead1.val<pHead2.val: tmp.next=pHead1#讓tmp具有指向 pHead1=pHead1.next else: tmp.next=pHead2 pHead2=pHead2.next tmp=tmp.next if pHead1==None: tmp.next=pHead2#這里不需要回圈，一個地址就可以進行全部的賦值 else: tmp.next=pHead1 return pHead.next
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2187.html
標籤：其他
上一篇：獲取表格資料轉換為JSON字串