怎么做？
面试中碰到了这么一个问题，让我来判断一个链表中是否存在环，怎么做。
这一看就是一个简单题，应该有几种解法，考虑到要有个优化的思路，我第一时间提到的是方法一。
方法一。借用哈希表来判断，每次访问一个节点，就把这个节点加入哈希表中。如果链表能顺利遍历到尾部，则无环。
否则必然会遇到一个节点已经在当前哈希表中，则说明链表有环。这个方法空间复杂度是O(n),时间复杂度也是O(n).
方法二。采用快慢指针法，定义两个指针，开始从链表头部往下走，慢指针每次走一步，快指针每次走两步，这样如果链表无环，则快指针会优先碰到链表尾部，若链表有环，则快慢指针会相遇。这个方法把空间复杂度降低到了O(1).
快慢指针法快指针走三步能判环吗？
这个问题当时面试的时候其实也比较急，回答的比较草率，直觉上就判断说不能，以为会有个环导致快指针一直错过慢指针。
现在回过头来细想，也可以用于链表判环。
首先我去leetcode上找了这个题目提交了一下，发现走三步确实是可以通过题目的所有测试用例的。题目链接
接下来就需要来理论证明一下这个点，为什么可以？
证明。
若不存在环，则快指针可以走到最后，可以判断这一情况。
若存在环，假设环的长度为L，入环点编码为0，入环点的下一个点编码为1，直至编码完所有环上的点。假设慢指针入环时，快指针位于x（0<=x<L）的位置。接下来两个指针继续走动，走动了m次，那么此时 慢指针位于m%L的位置，快指针位于(3m+x)%L的位置。
接下来需要判断x的范围是否真的是（0<=x<L），其实这个x也是有约束的假设从头部到慢指针入环，共走动了n次，那么此时两个指针相差的步数是2n步，在环内的距离应当时2n%L。也就是说x=2n%L。
现在就需要判断对于任意x=2n%L，是否存在自然数m使得 $m\bmod L=(3m+x)\bmod L$. 也就是$m \equiv (3m+x) mod(L)$, 根据同余定理，若$L|(3m+x-m)$则上式成立。
代入x=2n%L,并且变换一下式子得到，$(2m+2n\bmod L)\bmod L=0$。
对于任意自然数n是否存在自然数m使得这个等式成立呢？
接着变换式子。
$(2m\bmod L+2n\bmod L)\bmod L=0$，似乎陷入了死胡同。
回过头来看，在慢指针第一次入环时，快指针多走了2n步，接下来走了m次的话，快指针会继续多走2m步。此时快指针多走的步数是2(n+m)步。若2(n+m)恰好多走了t圈，则$2(n+m)=tL$.
在n确定的情况下，$m= tL/2-n$ 显然，因为t可以无穷大，对于任意自然数n，都会存在一个m来满足这个条件。
扩展
若快指针一次走k步呢？是否还能判断环？根据上面的公式$m= tL/(k-1) -n$。显然是可以的。
其实这题还有其他可以扩展的问题，内容丰富，不过这是后话了，这篇文章就先讲到这了。
