这篇文章主要介绍“怎么用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递归实现链表快速倒转”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。