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())