python怎么判断链表是否有环

1 链表有环是什么意思？

在判断是否有环前，需要先知道什么是链表中的环？

如下所示的链表有5个节点组成，框内的数字代表编号，也可理解为节点的地址。注意区分地址值和链表的数据域是完全不同的：

节点0指向节点3，而节点10又指向节点3，所以节点3就是环的入口，形成如下所示的一个环：

如果像下面这样遍历一个有环链表：

# head 是链表的头
while head:
    print(head.data)
    head = head.next

程序将会进入死循环，会在环内无穷的跑下去。

所以，研究如何判断链表是否有环，是一个非常有意义的课题，也是面试中常考的。

2 如何判断链表是否有环

通过哈希的方法，代码比较好理解：

class Solution(object):
    def hasCycle(self, head):
        s = set()
        tmp = head
        while tmp:
            if tmp in s:
                return True
            s.add(tmp)
            tmp = tmp.next 
        return False