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（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。