如何在链表中找到环的起始节点？

Question

从《Cracking the Coding Interview》一书中，有一个练习题如下：

给定一个循环链表，实现一个算法来返回循环开始的节点。

循环链表定义：一个（损坏的）链表，其中一个节点的下一个指针指向一个较早的节点，以便在链表中形成一个环。

算法的答案基本上是使用一个慢跑者和一个快跑者迭代遍历链表，以查看它是否循环。如果慢跑者和快跑者相遇，则表示它循环，然后您找到循环开始的节点。（如果它们不相撞，则快跑者最终将到达链表的末尾，这意味着没有循环。）

但是，书中关于找到循环开始节点的答案依赖于假设该链表具有大小为k的“非循环”部分。一旦慢跑者和快跑者相遇，您将把慢跑者移动到链表的头部。您以相同的速度迭代两个指针，直到它们相遇。它们相遇的位置就是循环开始的节点。

我的问题是，是否可能在不假设链表具有大小为k的“非循环”部分的情况下找到循环开始的节点？还是我必须假设有一个大小为k的“非循环”部分？

- Jessica

---

你可以自己回答。考虑大小为 n 的列表。循环的大小可以是 k，其中 0 <= k <= n，并从 i 开始，其中 0 <= i < n。考虑 k = 0 和 k = n 的情况以及跑步者的结束位置。 - Ripi2

"没有大小为k的非循环部分" <==> "存在大小为k的非循环部分，其中k = 0" <==> "整个链表是一个循环" <==> "快慢指针已经相遇" <==> "列表的第一个节点是循环的第一个节点。" 话虽如此，如果您担心初始条件，可以修改Floyd算法以在初始步骤后检测它们第一次碰撞的时间。如果碰撞节点与初始节点相同，则k = 0。 - Srini

如果没有“非循环”部分，你如何甚至定义“循环开始”的概念？你指的是第一个节点吗？ - ruakh

这个链表的结构是什么？我认为开始节点是唯一一个有两个节点指向它的节点。否则根本就没有所谓的开始。 - apple apple

它是否有任何时间/空间限制？ - apple apple

Answer 1

我有两个答案来回答这个问题，
第一个答案：
如果在大小为k的列表中有循环，如果你将其中一个指针从头部向前移动k步，另一个指针从头部开始一起移动，最终当其中一个指针完成一次完整的循环时，另一个指针刚好开始进入循环，这就是它们相遇于循环开头的原因。你需要做的就是计算循环中的节点数。
第二个答案：
通过以下示例介绍我的解决方案：
假设我们有这个列表：
使用快慢指针方法找到一个共同的指针。 假设他们在第7个节点相遇。 在执行此操作后，请记住节点7的下一个指针（作为列表的末尾）。 现在我们可以将其简化为另一个问题，即查找两个链表中的第一个公共元素，它们的结尾都是“node 8”，其中一个链表的头是列表的头（node 0），另一个链表的头是“node 8”。 它看起来像这样：

您可以通过以下步骤解决它：
1）获取第一个列表中节点的数量，让计数为c1。
2）获取第二个列表中节点的数量，让计数为c2。
3）获取计数差d = abs（c1-c2）。
4）现在从第一个节点开始遍历更大的列表，直到d个节点，以便从这里开始两个列表具有相等的节点数。
5）然后我们可以同时遍历两个列表，直到我们遇到一个公共节点。（请注意，获取公共节点是通过比较节点的地址完成的）。

- assaf.b

Answer 2

除非书中特别假设存在一个正的变量k，否则k也可以为零。

以下是关于k=0的非正式论证：

假设整个列表是一个循环。
如果快跑者是慢跑者的两倍速度，当慢跑者完成一次循环时，他们将相撞，而快跑者已经完成了两次循环。
如果你再让慢跑者从头开始跑，他们将立即在第一个节点上相撞。

- molbdnilo

Answer 3

我对那本书不熟悉，但我认为你没有正确阅读。可能k是循环大小，算法的工作方式如下：

1. 使用Floyd或Brent算法检测循环。（两者都在此处描述：https://en.wikipedia.org/wiki/Cycle_detection）
2. 让k成为循环大小的倍数，这样一旦进入循环，如果您进行k步，就会回到同一个节点。您可以在找到循环后测量这个值，也可以在查找循环时仅计算“快指针”和“慢指针”之间的步数差异。
3. 将2个指针放在列表头部（再次称它们为快速和慢速），并将“快速”指针向前移动k次。
4. 当快速和慢速指针指向不同节点时，以锁定步骤使它们同时前进，以便快速指针始终领先k步。

当慢指针进入循环时，算法将停止——即通过列表前进可以再次到达的第一个节点。

- Matt Timmermans

---

我也曾经认为我读错了这本书，但它确实说非循环部分的长度为k。但是感谢您提到了这种新的找到循环部分开头节点的方法。 - Jessica