文實例講述了Python實現鏈表反轉的方法。分享給大家供大家參考，具體如下：
Python實現鏈表反轉
鏈表反轉（while迭代實現）：
•鏈表的反轉引入一個cur_node變量，表示當前節點；同時需要引入一個變量new_link表示反轉後的新鏈表；while循環內還需中間變量tmp存放當前節點的後繼節點，防止原鏈表數據丟失。 •在while循環內(循環條件為 cur_node !=None，若設置為cur_node.next將導致最後一個節點無法反轉到新鏈表)： •首先需要將當前節點的後繼節點傳遞給中間變量tmp •當前節點指向新鏈表new_link •當前節點指向新鏈表new_link後，新鏈表頭結點更新為當前節點cur_node •將中間變量tmp傳遞給cur_node，開始新一輪循環 •循環結束後返回 new_link
<code>class Node(object):
def __init__(self, value=None, next=None):
self.value = value
self.next = next
@staticmethod
def reverse(head):
cur_node = head # 當前節點
new_link = None # 表示反轉後的鏈表
while cur_node != None:
tmp = cur_node.next # cur_node後續節點傳遞給中間變量
cur_node.next = new_link # cur_node指向new_link
new_link = cur_node # 反轉鏈表更新,cur_node為新的頭結點
cur_node = tmp # 原鏈表節點後移一位
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
/<code>
運行結果：
遞歸實現：
•遞歸實現與while實現不同在於遞歸首先找到新鏈表的頭部節點，然後遞歸棧返回，層層反轉 •首先找到新鏈表的頭結點（即遍歷到原鏈表的最後一個節點返回最後節點） •執行函數體後續代碼，將原鏈表中的尾節點指向原尾節點的前置節點 •前置節點的指針指向None(防止出現死循環) •返回新鏈表的頭部節點至上一層函數，重複以上操作
<code>def reverse2(head):
if head.next == None: # 遞歸停止的基線條件
return head
new_head = reverse2(head.next)
head.next.next = head # 當前層函數的head節點的後續節點指向當前head節點
head.next = None # 當前head節點指向None
return new_head
/<code>
關於Python實現鏈表反轉的方法_【迭代法與遞歸法】到此結束
分享到:
閱讀更多 IT小白進階之路 的文章
