在很多面试、笔试题目中，经常会出现一些关于单链表的题目，其中比较常见的主要就是问你如何判断一个单链表是否含有环。这是一个比较简单的问题，但是其实还可以问的更难一些的，比如：如何计算环的长度?如何找出环的起始位置?本文对这三个问题分别进行了分析。
是否含有环
这是一个最常见的问题，答案也是非常简单的，只要设置两个步长分别1和2的指针p,q，同时从head开始遍历整个链表，如果链表中含有环的话，则这两个指针p,q迟早会相遇;如果不存在环，则p,q永不相遇。
计算环的长度
这个问题承接于上一个问题，如果存在环的话，那么p,q相遇的位置一定是在环内部，则此时只需要固定p，让q以步长1继续往前走，记录其步数，直到再次遇到p，则q所走步数就是环的长度。
环的起始位置
这个问题同样是承接于第一个问题，这个方法稍微有些复杂，首先说明一个算法过程，然后再证明它。
假设p,q相遇在k，此时令p指向head(此时,q指向k,p指向head),然后p,q分别继续往下遍历(步长为1)，当p,q再次相遇的时候，相遇的节点就是环开始的位置。
证明:
假设链表中环的起始位置为S,head与S之间有μ个节点，环的长度1为n，p,q第一次相遇的位置为K，S与K之间有k个节点(k≤n)。假设p的步长为1,q的步长为2,令x表示q从head到K一共经过的节点数2。则:
x=μ+i⋅n+k
而对于p来说,因为起步长为1且p,q是同步运行的，所以p经过的节点数应该为2x:
2x=μ+j⋅n+k
根据上述的等式，解出μ=(j−2i)⋅n−k，将其代回x中，我们可以得到:
x=(j−i)⋅n⇒x+μ=(j−i)⋅n+μ
上述等式就说明了，当p,q相遇之后，再按步长为1,向前走μ个节点，就可以到达环的起始位置。
◻