时间复杂度 ，空间复杂度 。略。

在一个环中，如果两人速度不等且保持不变，那么总有一个时刻两者会相遇。应用此技巧，让一个slow指针每次移动一个结点，fast指针每次移动两个结点，如果两者最终能相遇，则说明单链表中存在环，如果fast走到了表尾，则说明不存在。

如果要求环长也好办，当两者相遇时，让其中一人保持不动，另一人再移动一圈，再次相遇时移动的路程即为环长。

但如何求出环的入口呢？

现已知单链表中存在环，设头结点与环入口距离为 ，从环入口到相遇结点的距离为 ，环长度为 ，slow指针在相遇前已经在环中移动了 圈，fast指针在相遇前已经在环中移动了 圈，那么slow指针移动的总路程为

fast指针移动的总路程为

由于fast移动速度为slow的两倍，路程也为两倍，则 ，两式相减得

这说明slow和fast指针移动路程都为环长的整数倍。

现增设一个指针slow1，让其从头结点开始，每次移动一个结点，与相遇结点处的slow指针同时出发。当slow1移动到环的入口，即距离为 时，slow移动的距离为

slow指针也一定停留在环的入口，它可以看作先移动了距离 ，即环入口处，又绕环移动了若干圈。

这说明，当slow和slow1相遇时，相遇结点必定为环的入口。

时间复杂度 ，空间复杂度 。