检测链表中循环开始的证明

Question

从 stackoverflow 内部和外部的几篇文章中，我开始知道如何检测链表中的循环，即循环的长度。我还找到了如何检测循环开始的方法。

这里再次提供步骤供参考。

检测循环：

有两个指针，通常称为兔子和乌龟。兔子移动2步，乌龟移动1步。如果它们在某个点相遇，那么肯定存在一个循环，并且相遇点显然在循环内。

查找循环长度：

将一个指针固定在交汇点，同时增加另一个指针，直到它们再次相同。随着您的进行而增加计数器，并且相遇时的计数器值将是周期的长度。

找到循环的开始

将一个指针指向列表的开头，并将另一个指针保留在交汇点。现在将两者都增加 1，交汇点就是循环的开始。我用纸上的一些案例验证了该方法，但我不明白为什么它应该有效。

有人可以提供数学证明来说明为什么这种方法有效吗？

Answer 1

如果您通过指向第一个节点的指针 (列表) 来表示列表

检测循环的算法描述如下：

1. 声明两个指针(pFast)和(pSlow)。
2. 使pSlow和pFast指向列表。
3. 直到 (pSlow)、(pFast) 或两者都指向 NULL：
4. 
5. 
6. 如果，则停止，因为刚刚发现了循环。
7. 如果已到达这一点（一个或两个指针均为 NULL），则列表中不存在循环。

让我们假设这个算法是正确的。
在此方案中，循环情况由下图表示：

请注意除第一个节点外的每个节点如何指向循环的开始，用其目标的编号减一来标记。因此，如果一个节点标记为 i 并且它不是循环的开始，则标记为 i-1 的节点将其指向下一个元素。

上面解释的算法可以被描述为一个循环，因为它的主要步骤（3）是一组重复的子步骤，直到满足退出条件。这迫使我们将 pFast 和 pSlow 表示为算法执行中迭代次数的函数 (t)。

如果列表没有循环，则指针位置将在 t 函数中描述为：

但是，有一个循环开始的节点，并且该函数停止描述指针的演变。假设该指针标记有 m，则循环包含节点（即 和 )，并在 < 时将 t=0 设置为迭代值img src="https://i.sstatic.net/DTxNP.gif" alt="在此处输入图像描述"> 然后：

如果一个指针确实足以使用所描述的算法检测循环，那么它必须至少存在方程的解 。

当且仅当 t 的值使得：

这以一个函数结束，，该函数生成 t 的值，这些值是上述方程的有效解:

由此证明，一个慢指针和一个快指针足以检测链表中的循环情况。

Answer 2

如果您不使用交汇点，您可以使“找到周期开始”证明变得更简单。
让第二个指针不是从“交汇点”开始，而是在第一个指针之前 M 步。 （其中M是循环的长度。）

这样，证明就非常明显了。当第一个指针到达循环开始时，第二个指针将正好领先 M 步：也在循环开始处。

Answer 3

SlowPointer 相遇前移动的距离 = x + y

fastPointer 相遇前移动的距离 = (x + y + z) + y = x + 2y + z

由于 fastPointer 的移动速度是 SlowPointer 的两倍，并且当到达集合点。

因此，通过使用简单的速度、时间和距离关系 2(x+y)= x+2y+z => x+2y+z = 2x+2y => x=z

因此，通过将slowPointer移动到链表的开头，并使slowPointer和fastPointer一次移动一个节点，它们都有相同的覆盖距离。

它们将到达链表中循环开始的点。

Answer 4

第二部分指出“要找到循环的开始，只需将一个指针移回列表的开头，然后迭代两者直到它们相遇”是错误的！

仅当快速指针恰好绕了一次循环时，它才是正确的 - 即循环开始之前的部分比循环的长度短 - 但如果它比算法长，那么它是正确的不起作用；你可能会陷入无限循环。

尝试使用包含 11 个元素的链表，其中第 11 个元素指向第 7 个元素：

1 1 -> 3 2 -> 5 3 -> 7 4 -> 9 5 -> 11 6 -> 8 7 -> 10 8 -> 7 9 -> 9 9

-- 检测到循环

将一个移回到开始位置并递增它们：
1 9 -> 1 2 10-> 3 11-> 4 7 -> 5 8 -> 6 9 -> 7 10 --> 8 11 --> 9 7 -> 10 8 -> 11 9 -> 11 7 10 --> 8 11 ->...

Answer 5

/* Algorithm : P2 is moving through the list twice as fast as P1.
   If the list is circular, it will eventually get around P1 and meet */

public boolean hasCycle()
{
  DoubleNode p1,p2;
  p1=p2=firstNode;    //Start with the first loop

  try
  {
    while (p2 != null)     //If p2 reaches end of linked list, no cycle exists
    {
        p1=p1.next;   //Move to next
        p2=p2.next.next; //Move to 2 steps next
        if(p1==p2)
           return true;     //p1 and p2 met, so this means that there is a cycle
    }
  }
  catch(NullPointerException npe)
  {
      //This means that p2 could not move forward
      return false;
  }

  return false;
}