链表是否有环，视频讲解

Day 40：判断链表是否有环

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

今天主要分析如何使用快慢指针判断链表是否有环，做到O(1)的空间复杂度，O(n)的时间复杂度，因此比哈希方法要更加节省内存空间。

快慢指针判断链表是否有环，代码其实非常清晰，但是理解背后的数学原理，才是真正写出代码的关键，也就说一旦理解原理，就会很自然的写出代码；相反，如果不理解，仅仅凭记忆，那么时间长了，就容易忘记，面试时就容易写错。

今天，重点也是理解背后的数学原理，下面这个视频参考网络，讲解的非常清晰，大家不妨看一遍：

代码网络上一搜有很多，在这里就不再贴了。