python算法題 鏈表反轉(zhuǎn)詳解
鏈表的反轉(zhuǎn)是一個(gè)很常見(jiàn)、很基礎(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
輸出：
3 2 1 0 2
第二種方式：遞歸
遞歸的思想就是：
head.next = None head.next.next = head.next head.next.next.next = head.next.next ... ...
head的向后指針的向后指針轉(zhuǎn)換成head的向后指針，依此類(lèi)推。
實(shí)現(xiàn)的關(guān)鍵步驟就是找到臨界點(diǎn)，何時(shí)退出遞歸。當(dāng)head.next為None時(shí)，說(shuō)明已經(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
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Python 能做很多無(wú)聊，但有意思的事情。本文為大家精心準(zhǔn)備了五個(gè)整蠱朋友的小程序，文中的示例代碼講解詳細(xì)，感興趣的小伙伴快動(dòng)手試一試2022-04-04
libreoffice python 操作word及excel文檔的方法
這篇文章主要介紹了libreoffice python 操作word及excel文檔的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07
使用python連接Linux服務(wù)器發(fā)送指定命令的示例代碼
這篇文章主要介紹了使用python連接Linux服務(wù)器發(fā)送指定命令,首先安裝paramiko庫(kù)，使用paramiko庫(kù)連接linux，使用paramiko庫(kù)上傳下載文件，結(jié)合示例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下2023-10-10
windows、linux下打包Python3程序詳細(xì)方法
這篇文章主要介紹了windows、linux下打包Python3程序詳細(xì)方法,需要的朋友可以參考下2020-03-03
Python機(jī)器學(xué)習(xí)利用隨機(jī)森林對(duì)特征重要性計(jì)算評(píng)估
本文是對(duì)隨機(jī)森林如何用在特征選擇上做一個(gè)簡(jiǎn)單的介紹。隨機(jī)森林非常簡(jiǎn)單，易于實(shí)現(xiàn)，計(jì)算開(kāi)銷(xiāo)也很小，更令人驚奇的是它在分類(lèi)和回歸上表現(xiàn)出了十分驚人的性能2021-10-10
python區(qū)塊鏈簡(jiǎn)易版交易完善挖礦獎(jiǎng)勵(lì)示例
這篇文章主要介紹了python區(qū)塊鏈簡(jiǎn)易版交易完善挖礦獎(jiǎng)勵(lì)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
這篇文章主要給大家介紹了關(guān)于Django管理員賬號(hào)和密碼忘記的完美解決方法，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起看看吧2018-12-12
Django使用echarts進(jìn)行可視化展示的實(shí)踐
可視化是將數(shù)據(jù)轉(zhuǎn)換成圖形或圖像在屏幕上顯示出來(lái)，本文主要介紹了Django使用echarts進(jìn)行可視化展示的實(shí)踐，感興趣的可以了解一下2021-06-06
這篇文章主要介紹了如何用python 批量重命名移動(dòng)多個(gè)文件，幫助大家更好的理解和學(xué)習(xí)使用python，感興趣的朋友可以了解下2021-03-03
利用Python實(shí)現(xiàn)自動(dòng)生成數(shù)據(jù)日?qǐng)?bào)
日?qǐng)?bào)，是大部分打工人繞不過(guò)的難題。對(duì)于管理者來(lái)說(shuō)，日?qǐng)?bào)是事前管理的最好抓手，可以了解團(tuán)隊(duì)的氛圍和狀態(tài)。本文將利用Python實(shí)現(xiàn)自動(dòng)生成數(shù)據(jù)日?qǐng)?bào)，感興趣的可以動(dòng)手嘗試一下2022-07-07