python判断链表是否有环的实例代码
先看下实例代码:
classNode: def__init__(self,value=None): self.value=value self.next=None classLinkList: def__init__(self,head=None): self.head=head defget_head_node(self): """ 获取头部节点 """ returnself.head defappend(self,value): """ 从尾部添加元素 """ node=Node(value=value) cursor=self.head ifself.headisNone: self.head=node else: whilecursor.nextisnotNone: cursor=cursor.next cursor.next=node ifvalue==4: node.next=self.head deftraverse_list(self): head=self.get_head_node() cursor=head whilecursorisnotNone: print(cursor.value) cursor=cursor.next print("traverse_over") defhasCycle(self,head): """ :typehead:ListNode :rtype:bool """ slow=fast=head whileslowandfastandfast.next: slow=slow.next fast=fast.next.next ifslowisfast: returnTrue returnFalse defmain(): l=LinkList() l.append(1) l.append(2) l.append(3) l.append(4) head=l.get_head_node() print(l.hasCycle(head)) #l.traverse_list() if__name__=="__main__": main()
知识点思考:
判断一个单链表是否有环,
可以用set存放每一个节点,这样每次访问后把节点丢到这个集合里面.
其实可以遍历这个单链表,访问过后,
如果这个节点不在set里面,把这个节点放入到set集合里面.
如果这个节点在set里面,说明曾经访问过,所以这个链表有重新走到了这个节点,因此一定有环
如果链表都走完了,把所有的节点都放完了.还是没有重复的节点,那说明没有环.
以上就是本次介绍的全部相关知识点内容,感谢大家的学习和对毛票票的支持。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。