如何判断是否存在环

这里我们考虑使用快慢指针的方式。快指针 fast 每次移动2个节点，慢指针 slow 每次移动一个节点。如果没有环，则 fast 指针将碰到 null，如果有环，则 fast 会在若干次移动后追上 slow。

为什么呢？假定单链表的长度为n，并且该单链表是环状的，那么第i次迭代时，p指向元素i mod n，q指向2i mod n。因此当i≡2i(mod n)时，p与q相遇。而i≡2i(mod n) => (2i - i) mod n = 0 => i mod n = 0 => 当i=n时，p与q相遇。

那么当p与q起点不同呢？假定第i次迭代时p指向元素i mod n，q指向k+2i mod n，其中0<k<n。那么i≡(2i+k)(mod n) => (i+k) mod n = 0 => 当i=n-k时，p与q相遇。

如何知道环的长度

由上一部分的分析我们可以知道，当起点相同时，i 等于 n 时两者会再次相遇，所以从相遇点开始，快慢指针再次相遇时经过的步骤数为环的长度。

如何找出环的连接点在哪里

假设第一个在环里的节点为节点 k，那么由上面的分析知道，满节点到达 k 节点时，快节点已经领先了慢节点 k mod n，所以相遇点在 i = n - k 处。这样，一个节点从相遇点开始，一个节点从头结点开始，以相同的速度行走，最终，经过k步，一个刚好从到达n，即回到了起点处，另外一个到达了 k，即起点处。