您好,登录后才能下订单哦!
python中怎么判断链表是否有环,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。
先看下实例代码:
class Node: def __init__(self,value=None): self.value = value self.next = Noneclass LinkList: def __init__(self,head = None): self.head = head def get_head_node(self): """ 获取头部节点 """ return self.head def append(self,value) : """ 从尾部添加元素 """ node = Node(value = value) cursor = self.head if self.head is None: self.head = node else: while cursor.next is not None: cursor = cursor.next cursor.next = node if value==4: node.next = self.head def traverse_list(self): head = self.get_head_node() cursor = head while cursor is not None: print(cursor.value) cursor = cursor.next print("traverse_over") def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ slow=fast=head while slow and fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return Falsedef main(): 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 里面 , 说明曾经访问过, 所以这个链表有重新 走到了这个节点, 因此一定有环
如果链表都走完了, 把所有的节点都放完了. 还是没有重复的节点, 那说明没有环.
看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注亿速云行业资讯频道,感谢您对亿速云的支持。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。