python遞歸實現鏈表快速倒轉

更新時間：2022年05月04日 10:23:17 作者：鵬鵬寫代碼

這篇文章主要為大家詳細介紹了python遞歸實現鏈表快速倒轉，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了python遞歸實現鏈表快速倒轉的具體代碼，供大家參考，具體內容如下

案例：實現如下鏈表進行倒轉

源代碼：

'''
Node 用于表示隊列中的節(jié)點；它包含兩個域。
val 表示節(jié)點的值。
next指向下一個節(jié)點
'''
#定義鏈表的數據結構
class Node:
? ? def __init__(self,val):
? ? ? ? self.next = None
? ? ? ? self.val ?= val

class ListUtility:#生成一個用來操作的鏈表
? ? def __init__(self):
? ? ? ? self.head = None
? ? ? ? self.tail = None
? ? ? ? pass
? ? def createList(self,nodeNum):
? ? ? ? if nodeNum <= 0:
? ? ? ? ? ? return None
? ? ? ? head = None
? ? ? ? val = 0
? ? ? ? node = None
? ? ? ? while nodeNum > 0:
? ? #如果head指針為空，代碼先構造隊列頭部，如果不為空，代碼構造節(jié)點對象，然后用上一個節(jié)點的next指針指向當前節(jié)點，從而將多個節(jié)點串聯(lián)成隊列。
? ? ? ? ? ? if head is None:
? ? ? ? ? ? ? ? head = Node(val)
? ? ? ? ? ? ? ? node = head
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? node.next = Node(val)
? ? ? ? ? ? ? ? node = node.next
? ? ? ? ? ? ? ? self.tail = node
? ? ? ? ? ? val += 1
? ? ? ? ? ? nodeNum -= 1
? ? ? ??
? ? ? ? self.head = head
? ? ? ? return head
? ??
? ? def printList(self,head):
? ? ? ??
? ? ? ? while head is not None:
? ? ? ? ? ? print("{0}->".format(head.val),end = " ")
? ? ? ? ? ? head = head.next
? ? ? ? print("null")
? ? ? ? ? ? ? ??
class ListReverse:
? ? def __init__(self, head):
? ? ? ? self.listHead = head
? ? ? ? self.newHead = None
? ? def recursiveReverse(self, node):
? ? ? ? #如果隊列為空或者只有一個節(jié)點，那么隊列已經倒轉完成
? ? ? ? if node is None or node.next is None:
? ? ? ? ? ? self.newHead = node
? ? ? ? ? ? return node
? ? ? ? '''
? ? ? ? 如果隊列包含多個節(jié)點，那么通過遞歸調用的方式，先把當前節(jié)點之后所有節(jié)點實現倒轉，
? ? ? ? 然后再把當前節(jié)點之后節(jié)點的next指針指向自己從而完成整個列表所有節(jié)點的導致
? ? ? ? '''
? ? ? ? head = self.recursiveReverse(node.next)
? ? ? ? head.next = node
? ? ? ? node.next = None
? ? ? ? return node
? ? def getReverseList(self):
? ? ? ? '''
? ? ? ? listHead是原隊列頭節(jié)點，執(zhí)行recursiveReverse后newHead指向新列表的頭結點，它
? ? ? ? 對應的其實是原列表的尾節(jié)點，而head指向新列表的尾節(jié)點
? ? ? ? '''
? ? ? ? self.recursiveReverse(self.listHead)
? ? ? ? return self.newHead
?utility = ListUtility()
head = utility.createList(10)
utility.printList(head)
#執(zhí)行倒轉算法，然后再次打印隊列，前后對比看看導致是否成功
reverse = ListReverse(head)
utility.printList(reverse.getReverseList()) ??

運行結果：