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递归实现链表快速倒转的详细内容...