Python實(shí)現(xiàn)鏈表反轉(zhuǎn)的方法分析【迭代法與遞歸法】
本文實(shí)例講述了Python實(shí)現(xiàn)鏈表反轉(zhuǎn)的方法。分享給大家供大家參考,具體如下:
Python實(shí)現(xiàn)鏈表反轉(zhuǎn)
鏈表反轉(zhuǎn)(while迭代實(shí)現(xiàn)):
- 鏈表的反轉(zhuǎn)引入一個(gè)cur_node變量,表示當(dāng)前節(jié)點(diǎn);同時(shí)需要引入一個(gè)變量new_link表示反轉(zhuǎn)后的新鏈表;while循環(huán)內(nèi)還需中間變量tmp存放當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn),防止原鏈表數(shù)據(jù)丟失。
- 在while循環(huán)內(nèi)(循環(huán)條件為 cur_node !=None,若設(shè)置為cur_node.next將導(dǎo)致最后一個(gè)節(jié)點(diǎn)無法反轉(zhuǎn)到新鏈表):
- 首先需要將當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)傳遞給中間變量tmp
- 當(dāng)前節(jié)點(diǎn)指向新鏈表new_link
- 當(dāng)前節(jié)點(diǎn)指向新鏈表new_link后,新鏈表頭結(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)cur_node
- 將中間變量tmp傳遞給cur_node,開始新一輪循環(huán)
- 循環(huán)結(jié)束后返回 new_link
class Node(object): def __init__(self, value=None, next=None): self.value = value self.next = next @staticmethod def reverse(head): cur_node = head # 當(dāng)前節(jié)點(diǎn) new_link = None # 表示反轉(zhuǎn)后的鏈表 while cur_node != None: tmp = cur_node.next # cur_node后續(xù)節(jié)點(diǎn)傳遞給中間變量 cur_node.next = new_link # cur_node指向new_link new_link = cur_node # 反轉(zhuǎn)鏈表更新,cur_node為新的頭結(jié)點(diǎn) cur_node = tmp # 原鏈表節(jié)點(diǎn)后移一位 return new_link link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9))))))))) root = Node.reverse(link) while root: print(root.value) root =root.next
運(yùn)行結(jié)果:
9
8
7
6
5
4
3
2
1
遞歸實(shí)現(xiàn):
- 遞歸實(shí)現(xiàn)與while實(shí)現(xiàn)不同在于遞歸首先找到新鏈表的頭部節(jié)點(diǎn),然后遞歸棧返回,層層反轉(zhuǎn)
- 首先找到新鏈表的頭結(jié)點(diǎn)(即遍歷到原鏈表的最后一個(gè)節(jié)點(diǎn)返回最后節(jié)點(diǎn))
- 執(zhí)行函數(shù)體后續(xù)代碼,將原鏈表中的尾節(jié)點(diǎn)指向原尾節(jié)點(diǎn)的前置節(jié)點(diǎn)
- 前置節(jié)點(diǎn)的指針指向None(防止出現(xiàn)死循環(huán))
- 返回新鏈表的頭部節(jié)點(diǎn)至上一層函數(shù),重復(fù)以上操作
def reverse2(head): if head.next == None: # 遞歸停止的基線條件 return head new_head = reverse2(head.next) head.next.next = head # 當(dāng)前層函數(shù)的head節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)指向當(dāng)前head節(jié)點(diǎn) head.next = None # 當(dāng)前head節(jié)點(diǎn)指向None return new_head
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對大家Python程序設(shè)計(jì)有所幫助。
- python算法題 鏈表反轉(zhuǎn)詳解
- Python數(shù)據(jù)結(jié)構(gòu)之翻轉(zhuǎn)鏈表
- 單鏈表反轉(zhuǎn)python實(shí)現(xiàn)代碼示例
- Python二叉搜索樹與雙向鏈表轉(zhuǎn)換實(shí)現(xiàn)方法
- python實(shí)現(xiàn)反轉(zhuǎn)部分單向鏈表
- Python3實(shí)現(xiàn)的反轉(zhuǎn)單鏈表算法示例
- Python 數(shù)據(jù)結(jié)構(gòu)之旋轉(zhuǎn)鏈表
- Python二叉搜索樹與雙向鏈表轉(zhuǎn)換算法示例
- python如何實(shí)現(xiàn)單鏈表的反轉(zhuǎn)
- python遞歸實(shí)現(xiàn)鏈表快速倒轉(zhuǎn)
相關(guān)文章
python3中apply函數(shù)和lambda函數(shù)的使用詳解
本文主要介紹了python3中apply函數(shù)和lambda函數(shù)的使用詳解,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-02-02詳解如何用OpenCV + Python 實(shí)現(xiàn)人臉識(shí)別
這篇文章主要介紹了詳解如何用OpenCV + Python 實(shí)現(xiàn)人臉識(shí)別,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2017-10-10關(guān)于pip install uwsgi安裝失敗問題的解決方案
這篇文章主要介紹了關(guān)于pip install uwsgi安裝失敗問題的解決方案,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-06-06Python使用metaclass實(shí)現(xiàn)Singleton模式的方法
這篇文章主要介紹了Python使用metaclass實(shí)現(xiàn)Singleton模式的方法,實(shí)例分析了Python基于metaclass實(shí)現(xiàn)單例模式的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-05-05Python使用matplotlib繪制圓形代碼實(shí)例
這篇文章主要介紹了Python使用matplotlib繪制圓形代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-05-05

Python被遠(yuǎn)程主機(jī)強(qiáng)制關(guān)閉后自動(dòng)重新運(yùn)行進(jìn)程的示例