algorithm - 链表循环检测算法

Question

我在网上阅读了一些关于如何找到链表中是否存在循环的面试问题，解决方案（弗洛伊德的循环查找算法）是有两个指针，一个比另一个快 2 倍，然后检查它们是否再次相遇。

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

Answer 1

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

对于链表套索检测算法，需要两个指针：

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

---

顺便说一句，套索是图论的终点技术，牛仔不是。

Answer 2

因为第一个（非移动）指针可能不在循环内，所以指针永远不会相遇。（请记住，循环可能仅包含列表的一部分。）

Answer 3

因为循环可能不包含第一个指针指向的元素。

例如，如果第一个指针指向元素 1，并且链接列表稍后有一个循环 (1->2->3->4->2)，那么您的算法将无法检测到它。