Python實現鏈表反轉的方法是什么

本篇內容主要講解“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

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

運行結果：

遞歸實現：

?遞歸實現與while實現不同在于遞歸首先找到新鏈表的頭部節點，然后遞歸棧返回，層層反轉
?首先找到新鏈表的頭結點（即遍歷到原鏈表的最后一個節點返回最后節點）
?執行函數體后續代碼，將原鏈表中的尾節點指向原尾節點的前置節點
?前置節點的指針指向None(防止出現死循環)
?返回新鏈表的頭部節點至上一層函數，重復以上操作

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

到此，相信大家對“Python實現鏈表反轉的方法是什么”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！