建站
咨詢
售后
建站咨詢
新聞中心
鏈表是面試?yán)锩娼?jīng)常涉及到的考點(diǎn)，因?yàn)殒湵淼慕Y(jié)構(gòu)相比于Hashmap、Hashtable、Concurrenthashmap或者圖等數(shù)據(jù)結(jié)構(gòu)簡單許多，對(duì)于后者更多面試的側(cè)重點(diǎn)在于其底層實(shí)現(xiàn)，本篇文章為大家分享一下使用python實(shí)現(xiàn)鏈表反轉(zhuǎn)的方法。
創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供靈璧網(wǎng)站建設(shè)、靈璧做網(wǎng)站、靈璧網(wǎng)站設(shè)計(jì)、靈璧網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)與制作、靈璧企業(yè)網(wǎng)站模板建站服務(wù)，10余年靈璧做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。
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é)果：
遞歸實(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實(shí)現(xiàn)鏈表反轉(zhuǎn)的方法_【迭代法與遞歸法】到此結(jié)束
分享題目：通過python實(shí)現(xiàn)鏈表反轉(zhuǎn)
新聞來源：http://fisionsoft.com.cn/article/cocspic.html
