您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“Python實(shí)現(xiàn)鏈表反轉(zhuǎn)的方法是什么”,感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“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)無(wú)法反轉(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,開(kāi)始新一輪循環(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é)果:
遞歸實(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
到此,相信大家對(duì)“Python實(shí)現(xiàn)鏈表反轉(zhuǎn)的方法是什么”有了更深的了解,不妨來(lái)實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。