怎么用python遞歸實現鏈表快速倒轉

這篇文章主要介紹“怎么用python遞歸實現鏈表快速倒轉”，在日常操作中，相信很多人在怎么用python遞歸實現鏈表快速倒轉問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”怎么用python遞歸實現鏈表快速倒轉”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

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

源代碼：

'''
Node 用于表示隊列中的節點；它包含兩個域。
val 表示節點的值。
next指向下一個節點
'''
#定義鏈表的數據結構
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指針為空，代碼先構造隊列頭部，如果不為空，代碼構造節點對象，然后用上一個節點的next指針指向當前節點，從而將多個節點串聯成隊列。
            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):
        #如果隊列為空或者只有一個節點，那么隊列已經倒轉完成
        if node is None or node.next is None:
            self.newHead = node
            return node
        '''
        如果隊列包含多個節點，那么通過遞歸調用的方式，先把當前節點之后所有節點實現倒轉，
        然后再把當前節點之后節點的next指針指向自己從而完成整個列表所有節點的導致
        '''
        head = self.recursiveReverse(node.next)
        head.next = node
        node.next = None
        return node
    def getReverseList(self):
        '''
        listHead是原隊列頭節點，執行recursiveReverse后newHead指向新列表的頭結點，它
        對應的其實是原列表的尾節點，而head指向新列表的尾節點
        '''
        self.recursiveReverse(self.listHead)
        return self.newHead
 utility = ListUtility()
head = utility.createList(10)
utility.printList(head)
#執行倒轉算法，然后再次打印隊列，前后對比看看導致是否成功
reverse = ListReverse(head)
utility.printList(reverse.getReverseList())

運行結果：

到此，關于“怎么用python遞歸實現鏈表快速倒轉”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！