温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

怎么用python递归实现链表快速倒转

发布时间:2022-05-05 09:27:45 来源:亿速云 阅读:101 作者:iii 栏目:开发技术

这篇文章主要介绍“怎么用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递归实现链表快速倒转

到此,关于“怎么用python递归实现链表快速倒转”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI