0

考虑以下链表：

1->2->3->4->5->6->7->8->9->4->...->9->4.....

上面的列表有一个循环如下：

[4->5->6->7->8->9->4]

在白板上绘制链表，我尝试手动解决不同的指针步骤，看看指针如何移动 -

(slow_pointer_increment, fast_pointer_increment)

因此，针对不同情况的指针如下：

(1,2), (2,3), (1,3)

前两对增量 - (1,2) 和 (2,3) 工作正常，但是当我使用对 (1,3) 时，算法似乎不适用于这对。是否有关于我们需要增加多少步骤才能使该算法成立的规则？

尽管我为较慢和较快的指针搜索了各种增量步骤，但到目前为止，我还没有找到一个相关的答案来说明为什么它不适用于此列表中的增量 (1,3)。

4

2 回答 2

2

如果指针增量和循环长度之间的差是互质数（即它们的最大公约数必须为 1），该算法才保证在任何位置找到一个循环。

对于一般情况，这意味着增量之间的差必须为 1（因为这是唯一与所有其他正整数互质的正整数）。

对于(1,3)，差是3-1=2，循环长度是2，2并且2不是互质数，因此算法不能保证找到循环。

理解这一点的关键在于，至少为了检查指针是否相遇，循环中慢速和快速指针的位置仅相对于彼此有关。也就是说，这两个可以认为是等价的：（两者的差为1）

slow fast             slow fast
   ↓ ↓                   ↓ ↓
 0→1→2→3→4→5→0     0→1→2→3→4→5→0

因此，我们可以将其视为slow保持不变并fast以 为增量移动的位置fastIncrement-slowIncrement，此时问题变为：

从任何位置开始，我们能否以某种速度（模周期长度）移动到特定位置？

或者，更一般地说：

我们能以某种速度（模周期长度）移动到每个位置吗？

仅当速度和周期长度互质时，这才是正确的。

例如，看速度为 4，循环长度为 6 - 从 0 开始，我们访问：
0, 4, 8%6=2, 6%6=0, 4, 2, 0, ...- GCD(4,6) = 2，我们只能访问每隔一个元素。
要查看实际情况，请考虑上面给出的示例的增量 (1,5) (difference = 4)，并看到指针永远不会相遇。

我应该注意到，至少据我所知，（1,2）增量被认为是算法的基本部分。

使用不同的增量（根据上述约束）可能会起作用，但它会远离“官方”算法并且会涉及更多工作（因为指向链表的指针必须迭代地递增，你不能递增它在一个步骤中超过 1）对于一般情况没有任何明显的优势。

于 2017-06-21T20:50:51.667 回答
0

伯恩哈德巴克的解释是正确的。我只是在添加它。

为什么指针之间的速度差和循环长度应该是互质数？

假设指针（比如v）和周期长度（比如L）之间的速度差异不是互质的。所以存在一个大于 1 的 GCD(v,L)（比如G）。

因此，我们有

  • v=指针之间的速度差
  • L=循环的长度（即循环中的节点数）
  • G=GCD(v,L)

由于我们只考虑相对位置，本质上slow是静止的并且fast以相对速度移动v。让我们fast在循环中的某个节点。

由于G是一个除数，L我们可以将周期划分为 G/L 部分。从所在位置开始划分fast。

现在，v是G（比方说v=nG）的倍数。每次fast指针移动时，它都会跳过n部分。因此，在每个部分中，指针都到达单个节点（基本上是一个部分的最后一个节点）。每次fast指针都会落在每个部分的结束节点上。参考下图

示例图片

正如 Bernhard 上面提到的，我们需要回答的问题是，我们能否以某种速度移动到每个位置？

如果我们有一个现有的 GCD，答案是否定的。正如我们所见，指针只会覆盖每个部分的最后一个节点。fast

于 2021-06-06T12:18:09.970 回答