快捷導(dǎo)航

python算法題鏈表反轉(zhuǎn)詳解

更新時(shí)間：2019年07月02日 08:54:47 作者：FOOFISH-PYTHON之禪

這篇文章主要介紹了python算法題鏈表反轉(zhuǎn),文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

鏈表的反轉(zhuǎn)是一個(gè)很常見、很基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)題，輸入一個(gè)單向鏈表，輸出逆序反轉(zhuǎn)后的鏈表，如圖：上面的鏈表轉(zhuǎn)換成下面的鏈表。實(shí)現(xiàn)鏈表反轉(zhuǎn)有兩種方式，一種是循環(huán)迭代，另外一種方式是遞歸。

第一種方式：循壞迭代

循壞迭代算法需要三個(gè)臨時(shí)變量：pre、head、next，臨界條件是鏈表為None或者鏈表就只有一個(gè)節(jié)點(diǎn)。

# 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 # 緩存當(dāng)前節(jié)點(diǎn)的向后指針，待下次迭代用
head.next = pre # 這一步是反轉(zhuǎn)的關(guān)鍵，相當(dāng)于把當(dāng)前的向前指針作為當(dāng)前節(jié)點(diǎn)的向后指針
pre = head # 作為下次迭代時(shí)的（當(dāng)前節(jié)點(diǎn)的）向前指針
head = next # 作為下次迭代時(shí)的（當(dāng)前）節(jié)點(diǎn)
return pre # 返回頭指針，頭指針就是迭代到最后一次時(shí)的head變量（賦值給了pre）

測(cè)試一下：

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

輸出：

第二種方式：遞歸

遞歸的思想就是：

head.next = None
head.next.next = head.next
head.next.next.next = head.next.next
...
...

head的向后指針的向后指針轉(zhuǎn)換成head的向后指針，依此類推。

實(shí)現(xiàn)的關(guān)鍵步驟就是找到臨界點(diǎn)，何時(shí)退出遞歸。當(dāng)head.next為None時(shí)，說明已經(jīng)是最后一個(gè)節(jié)點(diǎn)了，此時(shí)不再遞歸調(diào)用。

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

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

相關(guān)文章

一文帶你精通Python中exec函數(shù)的高級(jí)技巧
在?Python?中,exec?是一個(gè)內(nèi)置函數(shù),允許在運(yùn)行時(shí)動(dòng)態(tài)執(zhí)行?Python?代碼,本文將詳細(xì)介紹?Python?exec?函數(shù)的高級(jí)用法,包括動(dòng)態(tài)代碼生成、執(zhí)行外部文件等內(nèi)容,希望對(duì)大家有所幫助
2023-11-11
PHP統(tǒng)計(jì)代碼行數(shù)的小代碼
這篇文章主要為大家詳細(xì)介紹了PHP統(tǒng)計(jì)代碼行數(shù)的小代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2019-09-09
Python參數(shù)、參數(shù)類型、位置參數(shù)、默認(rèn)參數(shù)、可選參數(shù)舉例詳解
這篇文章主要介紹了Python?3.13中函數(shù)參數(shù)的不同類型,包括位置參數(shù)、默認(rèn)值參數(shù)、可變參數(shù)、關(guān)鍵字參數(shù)、命名關(guān)鍵字參數(shù)以及它們的組合使用規(guī)則,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下
2025-01-01
Python實(shí)現(xiàn)子類調(diào)用父類的方法
這篇文章主要介紹了Python實(shí)現(xiàn)子類調(diào)用父類的方法,解決子類覆蓋父類初始化方法而出現(xiàn)的不確定問題,可通過調(diào)用超類構(gòu)造方法的未綁定版本或者使用super函數(shù)來解決,需要的朋友可以參考下
2014-11-11
Python之京東商品秒殺的實(shí)現(xiàn)示例
這篇文章主要介紹了Python之京東商品秒殺的實(shí)現(xiàn)示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2021-01-01
Python 實(shí)現(xiàn) WebSocket 通信的過程詳解
WebSocket是一種在Web應(yīng)用程序中實(shí)現(xiàn)雙向通信的協(xié)議,與傳統(tǒng)的HTTP請(qǐng)求-響應(yīng)模型不同,WebSocket允許服務(wù)器主動(dòng)向客戶端推送數(shù)據(jù),實(shí)現(xiàn)實(shí)時(shí)性和互動(dòng)性,這篇文章主要介紹了Python 實(shí)現(xiàn) WebSocket 通信的過程詳解,需要的朋友可以參考下
2024-06-06
Python可視化神器pyecharts繪制?；鶊D
這篇文章主要介紹了Python可視化神器pyecharts繪制?；鶊D，即?；芰糠至鲌D，也叫桑基能量平衡圖，更多相關(guān)介紹具有一定的參考價(jià)值，需要的朋友可以參考一下
2022-07-07
Python中的兩個(gè)內(nèi)置模塊介紹
這篇文章主要介紹了Python中的兩個(gè)內(nèi)置模塊介紹,本文講解Python啟動(dòng)后默認(rèn)會(huì)加載的兩個(gè)內(nèi)建模塊,需要的朋友可以參考下
2015-04-04
python通過BF算法實(shí)現(xiàn)關(guān)鍵詞匹配的方法
這篇文章主要介紹了python通過BF算法實(shí)現(xiàn)關(guān)鍵詞匹配的方法,實(shí)例分析了BF算法的原理與Python實(shí)現(xiàn)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
2015-03-03
python編程Flask框架簡單使用教程
這篇文章主要為大家介紹了python編程中Flask框架簡單使用教程，有需要的朋友可以借鑒參考下希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪
2021-11-11