Linked List Cycle
链表存储在数组 next 中：节点 i 指向节点 next[i]，-1 表示链表在此处结束。头节点是节点 0。从头节点开始沿着链接前进，如果你回到访问过的节点，就返回 true；如果到达链表末尾，就返回 false。遍历过程中无法到达的节点不算，即使它们彼此相连形成循环也不算。
函数
- nextinteger-array
- 每个节点的链接：next[i] 是节点 i 后面的节点，或者是 -1
- 返回值boolean
- 如果从节点 0 开始遍历时再次访问某个节点，则为 true；如果到达 -1，则为 false
约束条件
1 ≤ next.length ≤ 104-1 ≤ next[i] ≤ next.length-1- 多个节点可能链接到同一个节点，而且有些节点可能无法从头节点到达。
示例
- 输入
- next = [1, 2, 3, 1]
- 输出
- true
- 解释
- 遍历顺序是 0、1、2、3，然后又回到 1。节点 1 被访问了两次，因此这个列表在节点 1、2 和 3 之间形成了一个循环。
- 输入
- next = [2, -1, 1]
- 输出
- false
- 解释
- 遍历路径依次经过 0、2、1，然后到达
-1：经过了三个不同的节点，接着到达终点，因此不存在循环。
- 输入
- next = [-1, 2, 1]
- 输出
- false
- 解释
- 节点 0 链接到
-1，所以这个列表只有一个节点。节点 1 和节点 2 在一个循环中相互链接，但从头节点开始遍历永远无法到达它们。
进阶
你还能在额外内存为 O(1) 的情况下，找到环开始的节点吗？
提示
逐个打开提示，每个都会多透露一点。
从节点 0 开始，沿着
next前进。没有环的列表会在-1处停止，但有环的列表永远不会停止。你需要记住什么，才能发现自己正在兜圈子？标记已访问的节点虽然可行，但需要为每个节点占用内存。另一种方法是让两个指针以不同的速度沿列表移动。如果列表中有循环，它们之间的距离会怎样变化？
每轮让
slow移动一个链接，让fast移动两个链接。如果fast或next[fast]是-1，就没有循环。如果两个指针最终指向同一个节点，就存在循环。
题解
带有环的列表永远不会到达 -1，所以你不能一直等到末尾。记住每个访问过的节点，可以用 O(n) 的内存检测循环。Floyd 的快慢指针只需两个整数就能检测循环，因为速度快一倍的指针一定会在循环内追上慢指针。
标记你访问过的节点
思路
从节点 0 开始遍历，离开每个节点时将其标记。到达已标记的节点，说明遍历已经回到之前的位置，之后会永远重复。在示例 1 中，你会标记 0、1、2 和 3，节点 3 指向节点 1，而节点 1 已被标记。
节点的编号从 0 到 n-1，因此长度为 n 的布尔数组可以用作已访问节点集合。遍历会在 n 步内停止：标记操作的时间复杂度为 O(n)，空间复杂度为 O(n)。
算法
- 创建一个长度为
n的布尔数组visited，所有元素都设为 false。 - 设置
node = 0。 - 当
node不为-1时，如果visited[node]已经为 true，就返回true。 - 否则，将
visited[node]设为 true，并移动到next[node]。 - 当遍历到
-1时，返回false。
def hasCycle(next):
visited = [False] * len(next)
node = 0
while node != -1:
if visited[node]:
return True # back at a node already on the path
visited[node] = True
node = next[node]
return False快慢指针（Floyd 环检测）
思路
slow 每轮沿着一条链接前进，fast 每轮沿着两条链接前进。如果列表结束，fast 会先到达 -1。如果存在环，fast 会进入环中并不断绕圈，直到 slow 到达。
两者都进入环后，fast 每轮恰好比 slow 多前进一个节点。它们之间的距离每轮缩短一个，因此最终会变成零，两个指针落在同一个节点上；它不可能越过零。
在示例 1 中，一轮后，slow 位于节点 1，fast 位于节点 2。两轮后，slow 位于节点 2，fast 位于节点 1。三轮后，两者都位于节点 3。
slow 会在 n 轮内进入环，并且它们会在 slow 绕完一圈之前相遇：时间复杂度为 O(n)，占用两个整数的内存。
算法
- 将
slow = 0和fast = 0设为初始值。 - 当
fast不等于-1且next[fast]不等于-1时，将slow移动一个链接，将fast移动两个链接。 - 每次移动后，如果它们位于同一个节点，则返回
true。 - 循环停止时，
fast已到达末尾：返回false。
def hasCycle(next):
slow = 0
fast = 0
# fast needs two links to move; if either is missing, the list ends.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
if slow == fast:
return True
return False
易错点和边界情况
- 一次移动两个节点的距离，让
fast前进，却没有同时检查两个节点是否存在。在读取next[next[fast]]之前，fast和next[fast]必须是有效节点，否则你会读取next[-1]，导致程序崩溃；在 Python 中则会悄悄读取最后一个元素。 - 移动指针之前就进行比较。两个指针都从节点 0 开始，因此在循环顶部进行检查会报告每个列表都存在循环。
- 检查整个数组，而不是沿着遍历路径检查。在
[-1, 2, 1]中，节点 1 和 2 形成的循环无法从头节点到达，因此答案是false。值重复也不代表存在循环：在[4, 4, 4, 4, -1]中，四个节点都指向节点 4。 - 以为循环必须回到头节点。在
[1, 2, 3, 4, 4]中，最后一个节点指向自身。
常见问题4
Floyd 的环检测是如何工作的？
两个指针从头部出发：一个每步移动一个链接，另一个每步移动两个链接。没有环时，快指针会到达末尾。有环时，两个指针最终都会进入环中，快指针每步缩短一个节点的距离，最终它们会在同一个节点相遇。
链表环的时间复杂度和空间复杂度是多少？
这两种方法都需要 O(n) 的时间。标记已访问的节点需要额外的 O(n) 内存。Floyd 快慢指针需要 O(1) 的内存：两个节点编号。
你能用哈希集合检测循环吗？
是的。对于由对象构成的列表，把每个节点引用放入哈希集合中，如果某个引用已在其中，就报告存在循环。它的时间复杂度为 O(n)，但会占用 O(n) 的内存，所以面试官接下来会要求你使用 Floyd 算法。
你能通过计算步数来检测循环吗？
对于这种数组形式，确实如此：没有环的列表会在 n 个链接内到达 -1，因此，如果走过 n 个链接后仍未到达末尾，就能证明存在环。由指针构成的列表无法提供 n，而且存在环时，先统计节点数永远无法完成。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def hasCycle(next):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
next = [1, 2, 3, 1]
预期输出
true