python算法題 鏈表反轉詳解
更新時間：2019年07月02日 08:54:47 作者：FOOFISH-PYTHON之禪
這篇文章主要介紹了python算法題 鏈表反轉,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
鏈表的反轉是一個很常見、很基礎的數(shù)據結構題，輸入一個單向鏈表，輸出逆序反轉后的鏈表，如圖：上面的鏈表轉換成下面的鏈表。實現(xiàn)鏈表反轉有兩種方式，一種是循環(huán)迭代，另外一種方式是遞歸。
第一種方式：循壞迭代
循壞迭代算法需要三個臨時變量：pre、head、next，臨界條件是鏈表為None或者鏈表就只有一個節(jié)點。
# encoding: utf-8 class Node(object): def __init__(self): self.value = None self.next = None def __str__(self): return str(self.value) def reverse_loop(head): if not head or not head.next: return head pre = None while head: next = head.next # 緩存當前節(jié)點的向后指針，待下次迭代用 head.next = pre # 這一步是反轉的關鍵，相當于把當前的向前指針作為當前節(jié)點的向后指針 pre = head # 作為下次迭代時的（當前節(jié)點的）向前指針 head = next # 作為下次迭代時的（當前）節(jié)點 return pre # 返回頭指針，頭指針就是迭代到最后一次時的head變量（賦值給了pre）
測試一下：
if __name__ == '__main__': three = Node() three.value = 3 two = Node() two.value = 2 two.next = three one = Node() one.value = 1 one.next = two head = Node() head.value = 0 head.next = one newhead = reverse_loop(head) while newhead: print(newhead.value, ) newhead = newhead.next
輸出：
3 2 1 0 2
第二種方式：遞歸
遞歸的思想就是：
head.next = None head.next.next = head.next head.next.next.next = head.next.next ... ...
head的向后指針的向后指針轉換成head的向后指針，依此類推。
實現(xiàn)的關鍵步驟就是找到臨界點，何時退出遞歸。當head.next為None時，說明已經是最后一個節(jié)點了，此時不再遞歸調用。
def reverse_recursion(head): if not head or not head.next: return head new_head = reverse_recursion(head.next) head.next.next = head head.next = None return new_head
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
在?Python?中,exec?是一個內置函數(shù),允許在運行時動態(tài)執(zhí)行?Python?代碼,本文將詳細介紹?Python?exec?函數(shù)的高級用法,包括動態(tài)代碼生成、執(zhí)行外部文件等內容,希望對大家有所幫助2023-11-11
這篇文章主要為大家詳細介紹了PHP統(tǒng)計代碼行數(shù)的小代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-09-09
Python參數(shù)、參數(shù)類型、位置參數(shù)、默認參數(shù)、可選參數(shù)舉例詳解
這篇文章主要介紹了Python?3.13中函數(shù)參數(shù)的不同類型,包括位置參數(shù)、默認值參數(shù)、可變參數(shù)、關鍵字參數(shù)、命名關鍵字參數(shù)以及它們的組合使用規(guī)則,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2025-01-01
這篇文章主要介紹了Python實現(xiàn)子類調用父類的方法,解決子類覆蓋父類初始化方法而出現(xiàn)的不確定問題,可通過調用超類構造方法的未綁定版本或者使用super函數(shù)來解決,需要的朋友可以參考下2014-11-11
這篇文章主要介紹了Python之京東商品秒殺的實現(xiàn)示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-01-01
Python 實現(xiàn) WebSocket 通信的過程詳解
WebSocket是一種在Web應用程序中實現(xiàn)雙向通信的協(xié)議,與傳統(tǒng)的HTTP請求-響應模型不同,WebSocket允許服務器主動向客戶端推送數(shù)據,實現(xiàn)實時性和互動性,這篇文章主要介紹了Python 實現(xiàn) WebSocket 通信的過程詳解,需要的朋友可以參考下2024-06-06
這篇文章主要介紹了Python可視化神器pyecharts繪制桑基圖，即?；芰糠至鲌D，也叫桑基能量平衡圖，更多相關介紹具有一定的參考價值，需要的朋友可以參考一下2022-07-07
這篇文章主要介紹了Python中的兩個內置模塊介紹,本文講解Python啟動后默認會加載的兩個內建模塊,需要的朋友可以參考下2015-04-04
這篇文章主要介紹了python通過BF算法實現(xiàn)關鍵詞匹配的方法,實例分析了BF算法的原理與Python實現(xiàn)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-03-03
這篇文章主要為大家介紹了python編程中Flask框架簡單使用教程，有需要的朋友可以借鑒參考下希望能夠有所幫助，祝大家多多進步早日升職加薪2021-11-11