鏈表的反轉是一個很常見、很基礎的數據結構題,輸入一個單向鏈表,輸出逆序反轉后的鏈表,如圖:上面的鏈表轉換成下面的鏈表。實現鏈表反轉有兩種方式,一種是循環迭代,另外一種方式是遞歸。
第一種方式:循壞迭代
循壞迭代算法需要三個臨時變量: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
以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061
微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元

