algorithm - 链表中的循环检测算法是如何工作的

Question

我知道这可以通过使用两个指针一慢一快来完成。但是我仍然不清楚的是，如果存在循环，那么我们如何确定慢指针和快指针在一个点上重叠。我想可能会有一些情况，当它们无限循环而不重叠时。是否存在两者必须重叠的循环数的方程式或上限。

Answer 1

忘记链表吧。并尝试假设您和您的伙伴正在环形跑道上进行比赛。但是他比你快2倍。当你跑完半圈，你的小伙伴就跑完一圈，当你跑完第一个圈，你快2倍的小伙伴就会站在你旁边。

现在用代表链表节点的点替换圆圈。

但是假设你没有循环列表，那么你的伙伴谁更快就会到达最后一个节点并完成比赛。