怎么在python中對鏈表進行反轉

本文章向大家介紹怎么在python中對鏈表進行反轉，主要包括怎么在python中對鏈表進行反轉的使用實例、應用技巧、基本知識點總結和需要注意事項，具有一定的參考價值，需要的朋友可以參考一下。

Python主要用來做什么

Python主要應用于：1、Web開發；2、數據科學研究；3、網絡爬蟲；4、嵌入式應用開發；5、游戲開發；6、桌面應用開發。

第一種方式：循壞迭代

循壞迭代算法需要三個臨時變量：pre、head、next，臨界條件是鏈表為None或者鏈表就只有一個節點。

# 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 # 緩存當前節點的向后指針，待下次迭代用
head.next = pre # 這一步是反轉的關鍵，相當于把當前的向前指針作為當前節點的向后指針
pre = head # 作為下次迭代時的（當前節點的）向前指針
head = next # 作為下次迭代時的（當前）節點
return pre # 返回頭指針，頭指針就是迭代到最后一次時的head變量（賦值給了pre）

測試一下：

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的向后指針的向后指針轉換成head的向后指針，依此類推。

實現的關鍵步驟就是找到臨界點，何時退出遞歸。當head.next為None時，說明已經是最后一個節點了，此時不再遞歸調用。

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

到此這篇關于怎么在python中對鏈表進行反轉的文章就介紹到這了，更多相關的內容請搜索億速云以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持億速云！