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

Question

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

注：本声明摘自以下网站：-

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

步骤1：找到循环后，两个指针都指向在循环内的交汇点的公共节点，
步骤2：现在，在它们之间移动一个指针（比如乌龟）到列表的头部，保持野兔指针在循环内的交汇点的相同位置。
步骤3：开始一次移动两个指针一个节点。它们都将相遇的地方是循环/循环的开始节点。

让我们在下面的图像中考虑案例2：

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

在应用所有步骤的过程中，在案例2中，我在步骤3中被塞住了

"下面是针对案例2的兔子和乌龟算法的计算结果。"

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

因此，根据步骤2，我保持快速指针不变，并将慢速指针移动到1（这是列表的头部）。

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

因为，它们都在“1”中，将每个指针移动一次，将永远不会结束，它将继续移动。

问题1。请问我是否理解了第三步中的错误？

问题2。我可以假设循环结束的节点是循环中的第一个节点吗？

Answer 1

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

顺便说一句，我认为你的困惑不是源于你犯的错误，而是源于你在问题中提供的伪代码的模糊性。即使你没有误解列表的头部，你也会执行一次伪代码的步骤3，并得出结论，指针将在标签为20的节点处相遇。（即列表第一个节点之后的那个）所以，我认为步骤3可作如下澄清。

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

如果遇到您提供的案例2这样的情况，在将其中一个指针移动到列表的开头后，迭代的条件将不会被满足，因为指针已经满足了。（列表的开头）

尽管您最初的第二季度非常不清楚，但让我根据您对其的澄清作为对我答案的评论来回答。

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