检查链表是否循环

check if linked list is circular

我阅读了如何检查链表是否为循环问题的解决方案。

对于:a->b->c->a : TRUE

对于:a->b->c->null : FALSE

解决方案使用更快和更慢的指针。快的每次跳 2 个单元格,慢的一次跳一个单元格。如果较快的指针到达 NULL 则为假,如果较慢的指针遇到较快的则为真。

我不明白的是,谁会同意这两个指针?如果列表包含 1000 万个细胞,您如何确定它们会相遇?如果两人在名单上无休止地擦肩而过,永远不会见面怎么办?

我知道这个解决方案是正确的,但我看到的所有地方都只有解释代码的作用或示例.. 我找不到任何证明这在每种情况下都有效的证据。

观察到的关键是,每走一步,两个指针之间的距离就会增加一个(一个指针移动一步,另一个指针移动两步)。

如果链表是循环的,循环长度为n个元素,当(1)它们都进入循环,(2)它们之间的距离是 n.

的倍数
  1. 由于指针都是从同一个元素开始的,如果链表是循环的,最终都会进入循环。显然一旦进入循环,他们将永远留在循环中。
  2. 一旦指针处于大小为 n 的循环中,向前(或向后)移动 n 个元素就是空操作。从元素 x 开始并执行 n 步将指针带回元素 x。从最初的观察我们知道两个指针之间的距离在每一步中增加一个。在某些时候,两个指针之间的距离是 n 的倍数,此时指针指向同一个元素。

如果一个循环列表有 10,000,000 个条目,并且一个指针比另一个指针高出 10,000,000 个位置,则它们相等。

你描述的算法还会发现列表是 ρ 形还是圆形,因为两个指针最终都会到达圆形区域。如果唯一的可能性是一个结束的列表和一个圆形的列表,那么您可以沿着列表移动一个指针,直到它到达 null 或等于头部。

这三种形状(-、o 和 ρ)是(非空)单向链表可以具有的仅有的三种形状:如果您从头开始迭代,要么到达终点,要么您将到达您已经访问过的元素。如果你重新访问头部,你会得到一个 o 形,如果你重新访问其他地方,你会得到一个 ρ 形。因此,能够处理所有三种形状可确保您的算法完成。

(在上面,我将 "list" 定义为您可以从头开始并迭代到达的节点集。这些节点可能是更大、更复杂的图形的一部分。 )