algorithm - 链表循环检测算法

Question

我在网上看了一些面试问题，关于如果链表中有循环你会如何找到，解决方案(Floyd's cycle-finding algorithm)是有两个指针，一个比另一个快 2 倍，并检查它们是否再次相遇.

我的问题是:为什么我不能只让一个指针固定不动，而是每次将另一个指针向前移动 1 步？

Answer 1

因为可能不是完整的 linkedList 在循环中。

对于一个链表lasso检测算法，你需要两个指针:

只要第一个指针在牛仔所在的位置，就不会检测到环路。但如果你一步一步地向前移动，它最终会进入循环。

---

顺便说一句，lasso 是图论中的技术终点，而 cowboy 不是。