检测链表中的循环

链表中的循环是指链表没有末尾的情况。当链表中存在循环时，最后一个指针不会像在单向链表或双向链表中那样指向 Null，也不会像在循环单向链表中那样指向链表的头。当循环存在时，它会指向某个其他节点，这也被称为链表循环。

让我们通过一个例子来理解循环。

在上面的图中，我们可以观察到链表中存在循环。这里，问题是我们需要检测作为循环起始点的节点。解决此问题的方案是：

• 首先，我们检测链表中的循环。
• 检测循环的起始节点。

检测循环

首先，我们将在链表中检测一个循环。为了理解这一点，我们将研究检测循环的算法。

步骤 1： 首先，我们将初始化两个指针，即 S 作为慢指针，F 作为快指针。最初，两个指针都指向链表中的第一个节点。

步骤 2： S 指针每次移动一个节点，而 F 指针每次移动两个节点。

步骤 3： 如果在某个时刻两个指针（S 和 F）指向同一个节点，则链表中存在循环；否则，不存在循环。

让我们可视化上述算法以获得更清晰的理解。

正如我们在上图中观察到的，S 和 F 两个指针都指向第一个节点。现在，我们将 S 指针移动一个，F 指针移动两个，直到它们相遇。如果 F 指针到达末尾节点，则表示链表中没有循环。

S 指针移动一个，而 F 指针移动两个，所以 S 指针指向节点 1，F 指针指向节点 9，如下图所示

由于两个指针不指向同一个节点，并且 F 指针没有到达末尾节点，所以我们将再次移动两个指针。现在，指针 S 将移动到节点 9，指针 F 将移动到节点 2，如下图所示

由于两个指针不指向同一个节点，所以我们再次增加指针。现在，S 将指向节点 4，F 将指向节点 7，如下图所示

由于两个指针不指向同一个节点，所以我们再次增加指针。现在，S 将指向节点 2，F 将指向节点 9，如下图所示

由于两个指针不指向同一个节点，所以我们再次增加指针。现在，S 将指向节点 3，F 也将指向节点 3，如下图所示

正如我们在上图中观察到的，两个指针都指向同一个节点，即 3；因此，链表中存在循环。

检测循环的起始点

在这里，我们需要检测循环的起源。我们将考虑在检测循环时讨论的相同示例。要检测循环的起始点，请考虑以下算法。

步骤 1： 将 'S' 移动到列表的开头，但 'F' 仍指向节点 3。

步骤 2： 将 'S' 和 'F' 同时向前移动一个节点，直到它们相遇。

步骤 3：它们相遇的节点就是循环的起始点。

让我们可视化上述算法以获得更清晰的理解。

首先，我们将指针 S 和 F 各增加一个；S 和 F 将分别指向节点 1 和节点 7，如下图所示

由于两个节点尚未相遇，所以我们再次将指针各增加一个节点，如下图所示

正如我们在上图中观察到的，S 指针指向节点 9，F 指针指向节点 2。所以我们再次将两个指针各增加一个节点。现在，S 将指向节点 4，F 将指向节点 9，如下图所示

正如我们在上图中观察到的，两个指针不指向同一个节点，所以我们再次将两个指针各增加一个节点。现在，指针 S 和 F 指向节点 2，如下图所示

由于两个指针都指向同一个节点，即 2；因此，我们得出结论，循环的起始节点是节点 2。

为什么这个算法有效？

考虑“l”表示循环的长度，它将衡量链接中的数量。

L：循环的长度

正如我们在上图中观察到的，有五个链接。

将 'm' 视为循环起始点到列表开头的距离。换句话说，'m' 可以定义为从起始节点到循环开始的节点的距离。因此，在上面的图中，m 是 4，因为起始节点是 8，循环开始的节点是 2。

将 'k' 视为在检测循环时 'S' 和 'F' 首次相遇点到循环起点的距离。在上面的链表中，'k' 的值将是 1，因为快慢指针首次相遇的节点是 3，而循环开始的节点是 2。

当“S”和“F”第一次相遇时，

假设慢指针覆盖的总距离是 distance_S，快指针覆盖的总距离是 distance_F。

distance_S = m + p*l + k

其中 S 覆盖的总距离是列表开头到循环起始点的距离、慢指针在循环中覆盖的距离以及从循环起始点到两个指针相遇的节点的距离之和。

distance_F = m + q*l + k (q>p 因为“S”的速度大于“F”的速度)

我们知道当“S”和“F”第一次相遇时，“F”的遍历速度是“S”指针的两倍；因此，“F”覆盖的距离将是“S”覆盖距离的两倍。在数学上，它可以表示为

distance_F = 2distance_S

上述方程可以写成

m + q*l + k = 2(m + p*l + k)

解上述方程，我们得到

m+k = (q-2p)*l, 这意味着 m+k 是 l（循环长度）的整数倍。

在 C 语言中实现循环检测。

在上述代码中，`detectloop()` 是用于检测链表中循环的函数名。我们传入了指向链表头节点的 `struct node` 类型的列表指针。在 `detectloop()` 函数内部，我们声明了两个 `struct node` 类型的指针，即 'S' 和 'F'，并将头节点的引用分配给它们。我们定义了一个 `while` 循环，其中我们检查 'S'、'F' 和 `F->next` 是否为 NULL。如果它们不为 NULL，则控制将进入 `while` 循环。在 `while` 循环中，'S' 指针递增一个节点，'F' 指针递增两个节点。如果 'F' 和 'S' 相等，则表示链表中存在循环。