计算机基础面试八股 · 第 64 题

1. 判环:快慢指针都从头出发,慢指针每次走 1 步,快指针每次走 2 步。快指针走到 null 说明无环;两者相遇说明有环。时间 O(n),空间 O(1)。
2. 找入口:相遇后,让一个指针回到表头,另一个留在相遇点,两者都每次走 1 步,再次相遇的节点就是环入口。
3. 原理:设表头到入口距离为 a,入口到相遇点距离为 b,环长为 L。相遇时慢指针走了 a+b,快指针走了 a+b+kL,且快指针路程是慢指针的 2 倍,所以 a+b = kL,即 a = kL - b = (k-1)L + (L-b)。从相遇点再走 a 步正好到达入口,与从表头走 a 步的指针在入口相遇。
4. 环长:相遇后让一个指针继续走,再回到相遇点所走的步数就是环长。

推导 a = (k-1)L + (L-b) 是关键得分点。