鏈表的反轉(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
輸出：
3
2
1
0
2
第二種方式：遞歸
遞歸的思想就是：
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
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
