LeetCode上面的题目#141：https://leetcode.com/problems/linked-list-cycle/。
题目大意：给定一个单链表，判断其中是否有环。
这道题还有一个变种#142：https://leetcode.com/problems/linked-list-cycle-ii/。
题目大意：给定一个单链表，如果其中有环，输出环的入口节点，否则输出null。
对于这种题目，稍微有点经验的人都会想到采用双指针来解决，甚至LeetCode上有一个专门的topic，就叫做Two Pointers。用双指针判断迭代序列内是否存在环的算法即Floyd环检测算法。
迭代序列中环的描述
令S为有限集合。如果有一个f为S映射到自身的函数，并且取任意一个a[0]∈S作为起始元素，那么序列A：
a[0], a[1]=f(a[0]), a[2]=f(a[1]), ..., a[i]=f(a[i-1]), ...
中一定存在环。
举个例子，设S={0,1,2,3,4,5,6,7,8}，f如下面的图中所示。如果取a[0]=8或a[0]=2作为起始元素，那么产生的序列A中就会存在一个环6→3→1。
虽然上面画成了有向图的样子，但图论中的环与本文讨论的环是两码事。图论中检测环的方法主要有DFS和拓扑排序，这里就不提了。
令μ为环的起始元素的最小下标（也就是环的入口点），λ为环的长度。Floyd环检测算法的目的就是要在序列A中确定是否有环，如果有，就输出μ和λ。
算法流程
又叫做“龟兔赛跑算法”。
- 判断是否有环
使用两个指针hare（兔子）和tortoise（乌龟），从序列的起始元素a[0]开始同步向后移动。hare每次移动两个元素，tortoise每次移动一个元素。如果两个指针在移动若干次后指向的元素值相同，那么序列中有环。
证明：如果有环存在的话，那么对于任意的i≥μ，都有a[i]=a[i+kλ]，k是正整数。对于特定的k，总会存在一个i=kλ满足条件，此时a[i]=a[2i]。所以可以利用步长分别为1和2的两个指针来判断。
- 确定λ和μ
一旦hare和tortoise指向的元素值相同，就将tortoise指针移回a[0]处，然后它们同步以步长1向后移动，直到它们指向的元素值再次相同。此时tortoise指向的位置就是μ，即环的入口点。
证明：如果在上面判断有环的过程中，tortoise走过了距离d，那么hare就走过了距离2d，并且它们之间的差值正好是kλ。将tortoise重置后，如果要满足a[j]=a[j+2d]（j从0开始），根据定义，这个最小的j值也恰好就是μ。
然后，让tortoise停在μ处不动，hare继续以步长1向后移动，直到它们指向的元素值再次相同。此时hare走过的步数就是λ，即环的长度。
该算法的时间复杂度是O(μ+λ)，空间复杂度是O(1)。
Linked List Cycle II的解法
单链表就是一种特殊的迭代序列，基于上面的思想就很容易写出下面的代码了。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
slow = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}
