loops - 在单链接列表中检测循环的开始？

Question

有什么方法可以使用不超过两个指针在链接列表中找出循环的起点吗？
我不想访问每个节点并标记为已看到并报告已经看到的第一个节点，还有其他方法吗？

Answer 1

作为面试测验，我已经听到了这个确切的问题。

最优雅的解决方案是:

将两个指针都放在第一个元素上(分别称为A和B)

然后继续循环::

将A前进到下一个元素

再次将A前进到下一个元素

将B前进到下一个元素

每次更新指针时，请检查A和B是否相同。
如果在某些时候指针A和B相同，那么您就有一个循环。
这种方法的问题是，您可能最终会在循环中移动两次，但使用指针A时最多只能进行两次

如果要实际找到具有两个指向它的指针的元素，则难度更大。我会不知所措，说只有两个指针是不可能的，除非您愿意多次重复链接列表。

拥有更多内存的最有效方法是将指向数组和元素的指针放在数组中，对其进行排序，然后寻找重复的对象。