如何使用两个指针找到链接列表中是否存在循环[[副本]

Floyd's cycle detection algorithm ,也称为“龟兔算法”。这个想法是设置一个指针(“乌龟”)到 每走一步,“乌龟”指针前进一个位置,“兔子”前进两步。每次迭代后,都会检查指针是否指向 相同的节点。如果发生这种情况,则该节点必须是循环的一部分。

为了找到循环的开始,两个指针中的一个被重新定位到 列表的开头,而另一个则保留在当前位置。然后两个指针

每次迭代移动一个指针1个节点,每次迭代移动另一个指针2个节点。如果快速节点看到null,则不存在循环;如果快速指针看到慢速指针,则存在循环。解决了的。

这个解决方案是模仿乌龟和野兔的著名解决方案。