如何判断一个链表是否有环?

有一次面试有被问到这个问题, 有思路就好

先思考一下，如果存在环，那么当前链表会有什么特点？

存在环就说明链表的尾节点不是指向 null，而是指向了链表中的另一个节点，只有这样才会构成环

知道了链表有环的特点了(这里其实就是特征点),就好办,想办法能探测到这个特征就ok了

解决方法

哈希法 _{最简单的,很多公司的业务也可以这么做}

直接遍历链表，并且判断当前节点是否存在于哈希表中，如果存在，那就说明当前链表存在环，如果不存在，那么我们就将当前链表节点存入哈希表中，并继续往后遍历，直到发生哈希碰撞为止。如果存在环，那么就一定会发生哈希碰撞，如果不存在环，那么就一定有一个节点的 next 指针指向 null，所以循环也会终止。

从处理方法上可以看到以下缺点:

• 需要申请额外的空间内存储Hash值
• 最坏的情况下,可以到最后才能检测到,因为是遍历链表

空间复杂度是O(n)

快慢指针法

我们设想一下这么个场景，比如说有两个人在圆形跑道上跑步，一个人一秒钟跑一米，另一个人一秒钟跑两米，然后他们两同时开始并且一直跑，那么他们会不会相遇呢？

答案是只要体力允许，他们两一定会在某一个点相遇；相反，如果是直线跑道，那么他们就不可能相遇。所以我们可以将这个思想利用起来，这就是快慢双指针法。

故一定是圆形,快慢指针才有效

所以很容易得出以下思路: 定义两个指针，一个 slow 指针，一次走一步；另一个 fast 指针，一次走两步。如果可以在某一个点满足 slow=fast，那么就说明存在环，否则 fast 指针必然先到到终点。

进阶思考: 如何判断链表中环的位置 | 换种说法,如何找到环的入口位置?

1. 很简单,如果使用哈希法,冲突的位置就是环的位置
2. 快慢指针法,这个不行,因为快慢指针相遇的位置不一定是环的位置

拓展思考:为什么快指针只走 2 步，而不是 3 步，4 步，甚至更多呢？

如果快指针走多了会导致一个问题: 当快慢指针相遇时，我们无法知道快指针在环形里面走了多少圈，也无法知道慢指针在环形里面走了多少圈，这会导致很难推断环的入口位置。

所以快指针走 2 步时,当慢指针也入环之后，每走一次，慢指针都会和快指针拉开 1 步距离；而反过来想，相当于是快指针每次都在以缩短 1 步的距离来追赶 slow 指针，因为每次只缩短 1 步，所以快慢指针一定不会出现错过相遇点的情况。

那,如何解决呢?

答案是,再引入一个指针.

如果 slow 和 fast 相遇了，那么这时候我们再定义一个指针指向链表起点，一次走一步，slow 指针也同步继续往后走，那么这两个指针就一定会在链表的入口位置相遇。