欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python實現(xiàn)鏈表反轉(zhuǎn)的方法分析【迭代法與遞歸法】

 更新時間:2020年02月22日 12:29:01   作者:授我以驢  
這篇文章主要介紹了Python實現(xiàn)鏈表反轉(zhuǎn)的方法,結(jié)合實例形式分析了Python迭代法與遞歸法實現(xiàn)鏈表反轉(zhuǎn)的相關(guān)操作技巧與注意事項,需要的朋友可以參考下

本文實例講述了Python實現(xiàn)鏈表反轉(zhuǎn)的方法。分享給大家供大家參考,具體如下:

Python實現(xiàn)鏈表反轉(zhuǎn)

鏈表反轉(zhuǎn)(while迭代實現(xiàn)):

  • 鏈表的反轉(zhuǎn)引入一個cur_node變量,表示當(dāng)前節(jié)點;同時需要引入一個變量new_link表示反轉(zhuǎn)后的新鏈表;while循環(huán)內(nèi)還需中間變量tmp存放當(dāng)前節(jié)點的后繼節(jié)點,防止原鏈表數(shù)據(jù)丟失。
  • 在while循環(huán)內(nèi)(循環(huán)條件為 cur_node !=None,若設(shè)置為cur_node.next將導(dǎo)致最后一個節(jié)點無法反轉(zhuǎn)到新鏈表):
    • 首先需要將當(dāng)前節(jié)點的后繼節(jié)點傳遞給中間變量tmp
    • 當(dāng)前節(jié)點指向新鏈表new_link
    • 當(dāng)前節(jié)點指向新鏈表new_link后,新鏈表頭結(jié)點更新為當(dāng)前節(jié)點cur_node
    • 將中間變量tmp傳遞給cur_node,開始新一輪循環(huán)
    • 循環(huán)結(jié)束后返回 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 # 當(dāng)前節(jié)點
    new_link = None # 表示反轉(zhuǎn)后的鏈表
    while cur_node != None:
      tmp = cur_node.next # cur_node后續(xù)節(jié)點傳遞給中間變量
      cur_node.next = new_link  # cur_node指向new_link
      new_link = cur_node  # 反轉(zhuǎn)鏈表更新,cur_node為新的頭結(jié)點
      cur_node = tmp  # 原鏈表節(jié)點后移一位
    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

運(yùn)行結(jié)果:

9
8
7
6
5
4
3
2
1

遞歸實現(xiàn):

  • 遞歸實現(xiàn)與while實現(xiàn)不同在于遞歸首先找到新鏈表的頭部節(jié)點,然后遞歸棧返回,層層反轉(zhuǎn)
  • 首先找到新鏈表的頭結(jié)點(即遍歷到原鏈表的最后一個節(jié)點返回最后節(jié)點)
  • 執(zhí)行函數(shù)體后續(xù)代碼,將原鏈表中的尾節(jié)點指向原尾節(jié)點的前置節(jié)點
  • 前置節(jié)點的指針指向None(防止出現(xiàn)死循環(huán))
  • 返回新鏈表的頭部節(jié)點至上一層函數(shù),重復(fù)以上操作
  def reverse2(head):
    if head.next == None: # 遞歸停止的基線條件
      return head
    new_head = reverse2(head.next)
    head.next.next = head # 當(dāng)前層函數(shù)的head節(jié)點的后續(xù)節(jié)點指向當(dāng)前head節(jié)點
    head.next = None # 當(dāng)前head節(jié)點指向None
    return new_head

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程

希望本文所述對大家Python程序設(shè)計有所幫助。

相關(guān)文章

  • Python被遠(yuǎn)程主機(jī)強(qiáng)制關(guān)閉后自動重新運(yùn)行進(jìn)程的示例

    Python被遠(yuǎn)程主機(jī)強(qiáng)制關(guān)閉后自動重新運(yùn)行進(jìn)程的示例

    要實現(xiàn)Python程序在被遠(yuǎn)程主機(jī)強(qiáng)制關(guān)閉后能夠自動重新運(yùn)行,我們可以采用幾種方法,但最直接且常用的方法之一是結(jié)合操作系統(tǒng)級的工具或腳本,這篇文章主要介紹了Python被遠(yuǎn)程主機(jī)強(qiáng)制關(guān)閉后怎么自動重新運(yùn)行進(jìn)程,需要的朋友可以參考下
    2024-08-08
  • 最新評論