algorithm - 检测链表中循环中的第一个节点

Question

最近，我完成了检测循环中第一个节点的算法，如下所述:-

注意:本声明摘自网站:-

http://javabypatel.blogspot.in/2015/12/detect-loop-in-linked-list.html

现在重点是，我们将如何知道循环的起始节点。
第 1 步:找到循环后，两个指针都指向位于交汇点的公共(public)节点 内循环，
第 2 步:现在，将其中的一个指针(比如乌龟)移动到列表的头部，保持兔子 指针位于循环内交汇点的同一位置。
第 3 步:开始将两个指针一次移动一个节点。他们相遇的地方就是开始 循环/循环的节点。

让我们考虑下图中的案例 2:-

http://4.bp.blogspot.com/-79s5PBIexDE/Vmac8UlposI/AAAAAAAAAvQ/ejHRpGv_OLY/s1600/loop-in-linked-list-example.png

在应用所有步骤时，在案例 2 中，我陷入了第 3 步

“以下是针对案例 2 的 Hare and Tortoise 算法的计算结果。”

更快 - 1 更慢 - 1
快 - 5 慢 - 20
更快 - 22 更慢 - 5
更快 - 20 更慢 - 18
更快 - 18 更慢 - 22
更快 - 1 更慢 - 1 - 两个指针在这里相遇..

因此，按照第 2 步，我保持 Faster Pointer 不变，并将 Slow Pointer 移动到 1(这是列表的头部)。

因此，按照第 3 步，我将每个指针一个一个递增。

因为它们都在“1”，所以每个指针移动一个，永远不会结束，它会一直移动。

Q1.请问，我在第 3 步中是否理解错了什么？

Q2.我可以假设循环结束的节点是循环中的第一个节点吗？

Answer 1

直到最后一步，您似乎都正确地追踪了给定的算法。不过，在最后一步，我认为您将术语列表头部 误认为是指向列表第一个元素的指针。因此，您可能已经推断出循环永远不会结束，因为两个指针将以相同的速度移动并且一个指针将领先另一个指针 1。但是，我相信使用了列表的头部引用列表中的第一个元素，而不是指向第一个元素的指针。

顺便说一句，我认为您的困惑不是源于您犯的错误，而是源于您在问题中提供的伪代码的歧义。即使您没有误解列表的头部，您也会执行一次伪代码的第 3 步，并得出结论，指针将在标签为 20 的节点处相遇。(即列表第一个节点之后的节点)因此，我认为第 3 步可以使用如下说明。

第 3 步: 当兔子和乌龟在不同的单元格中时，将两个指针一次移动一个节点。

这样更正，如果遇到你提供的case 2这样的情况，将其中一个指针移动到列表的开头后，迭代的条件不会满足，因为指针已经见面了。 (由于循环的开始在列表的开头)

尽管您最初的Q2 很不清楚，但让我根据您对它的澄清作为对我的回答的评论来回答它。

在您提供的链接中，显示汇合点 M 兔子和乌龟指针 在您提供的伪代码的第 1 步之后 与循环开始的确切距离为列表的第一个元素有。 (即上图中的距离 p 和 r 相等)因此，如果一个指针放在列表的开头而另一个指针保持在它们的交汇点，如果两者都移动 1，只要它们不在列表的相同节点，是的，如果存在这样的循环，您可以假设它们相遇的地方将是列表中循环的开始。