在很多面试、笔试题目中，经常会出现一些关于单链表的题目，其中比较常见的主要就是问你如何判断一个单链表是否含有环。这是一个比较简单的问题，但是其实还可以问的更难一些的，比如：如何计算环的长度?如何找出环的起始位置?本文对这三个问题分别进行了分析。
是否含有环
这是一个最常见的问题，答案也是非常简单的，只要设置两个步长分别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\)之间有\(\mu\)个节点，环的长度1为\(n\)，\(p,q\)第一次相遇的位置为\(K\)，\(S\)与\(K\)之间有\(k\)个节点(\(k\le n\))。假设p的步长为1,q的步长为2,令\(x\)表示\(q\)从head到\(K\)一共经过的节点数2。则:
而对于\(p\)来说,因为起步长为1且\(p,q\)是同步运行的，所以\(p\)经过的节点数应该为\(2x\):
根据上述的等式，解出\(\mu=(j-2i)\cdot n-k\)，将其代回\(x\)中，我们可以得到:
上述等式就说明了，当\(p,q\)相遇之后，再按步长为1,向前走\(\mu\)个节点，就可以到达环的起始位置。
\(\Box\)