导语：常见Java问题及笔试题（二十八）——如何判断单链表有环（含数学证明）

判断链表是否有环应该是面试官经常问的问题。

方法很简单：设置两个指针fast和slow，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。

下面先证明一下

数学证明：假设某一时刻fast和slow都已经进入 了环，环的长度是K。分别编号为0,1,2......k-1。

（1）首先来看两节点初始都在节点0的时候的情况，时间t的时候两个指针的位置节点分别为t%k和2t%k，节点相遇的时候有 t%k=2t%k。这个模型肯定有解，比如t等于k的整数倍这个时候正好相遇在起点。

（2）现在看看两个指针在刚开始的时候不是同时进入环的情况，因此将模型修改为 t%k=(2t%k+b)%k。我们知道b是小于k的。所以上式可以写为，如下图所示：

从数学上证明之后，我们就可以安心写代码了。

都是基础题，大牛请略过！！！

本文内容由快快网络小岑创作整理编辑！