c++ - 如何在链表中找到循环开始的节点？

Question

从破解编码面试中，有一个练习说：

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

循环链表的定义：一个（损坏的）链表，其中一个节点的next指针指向一个更早的节点，从而在链表中形成一个循环。

算法的答案基本上是使用一个慢而快的跑步者来遍历链表，看看它是否循环。如果慢跑者和快跑者发生碰撞，它就会循环，所以你会在循环的开头找到节点。（如果它们不碰撞，那么快跑者最终会到达链表的末尾，这意味着没有循环。）

但是这本书寻找循环开始处节点所在位置的答案依赖于链表具有大小为 k 的“非循环”部分的假设。一旦慢跑者和快跑者发生碰撞，您将慢跑者移动到链表的头部。您以相同的速度迭代两者，直到它们发生碰撞。它们碰撞的地方是循环开始的节点。

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

标签： c++algorithmlinked-list

Answer 1

对于这个问题，我有 2 个答案，
一个：
如果您在大小为 k 的列表中有循环，如果您从头部移动指针 k 步，从头部移动另一个指针并将它们一起移动，最后当其中一个执行一个完整的循环，另一个刚刚开始循环，然后这就是他们在循环开始时相遇的原因。您所需要的只是计算循环中的节点。
第二：
我通过示例介绍我的解决方案：
假设我们得到了这个列表：
使用更快和更慢的运行器方法找到一个公共指针。让我们假设它们在节点 7 中相遇。在你这样做之后，记住节点 7 的下一个指针（作为列表的末尾）。现在我们可以减少到另一个问题来解决这个问题，那就是在两个链表中找到第一个公共元素，它们的末尾是“节点 8”的指针，其中一个的头是链表的头（节点 0），另一个列表头是“节点 8”。
它看起来像这样：

您可以通过以下步骤解决它：
1）获取第一个列表中的节点数，设 count 为 c1。
2) 获取第二个列表中的节点数，设 count 为 c2。
3) 获得计数差 d = abs(c1 – c2)
4) 现在从第一个节点遍历更大的列表直到 d 个节点，以便从这里开始两个列表的节点数相等。
5）然后我们可以并行遍历两个列表，直到遇到一个公共节点。（请注意，通过比较节点的地址来获得公共节点）。