怎么判断一个链表是否有环？空间复杂度 O(1) 怎么做？

核心思路：快慢指针法

判断链表是否有环最经典且满足O(1)空间复杂度的方法是快慢指针，也叫"龟兔赛跑"算法。我们定义两个指针同时从链表头出发，慢指针每次走一步，快指针每次走两步。如果链表有环，快指针最终会追上慢指针；如果无环，快指针会先到达链表尾部。

为什么快慢指针有效

想象一下操场上的环形跑道。两个人同时从起点出发，跑得快的人最终会"套圈"跑得慢的人。在链表的环中也是同样的道理——快指针每次多走一步，相当于相对速度是1步/次，所以如果有环，它们必然在有限步数内相遇。

从数学角度看，假设环外长度为a，环内长度为b。当慢指针进入环时，快指针已经在环内走了若干距离。由于快指针比慢指针快一倍，它们最终会在环内某点相遇。这个推理的关键在于：快指针永远不会"跳过"慢指针，因为相对速度是1，每次移动它们之间的距离只会减少1。

具体实现步骤

1. 初始化slow和fast都指向头节点

2. 循环条件：fast不为空且fast.next不为空

3. 每次循环：slow = slow.next，fast = fast.next.next

4. 如果slow == fast，说明有环

5. 如果循环结束未相遇，说明无环

代码示例（JavaScript）

```javascript

function hasCycle(head) {

if (!head || !head.next) return false;

let slow = head;

let fast = head;

while (fast && fast.next) {

slow = slow.next;

fast = fast.next.next;

if (slow === fast) return true;

}

return false;

}

```

进阶问题：找到环的入口

如果需要找到环的入口节点，可以在快慢指针相遇后，让一个指针从头开始，另一个从相遇点开始，每次都走一步，它们再次相遇的位置就是环的入口。

这个结论的数学推导很简单：设环外长度为a，相遇点时慢指针走了a+x，快指针走了a+x + n*b（n圈环）。因为快指针速度是慢指针的2倍，所以2(a+x) = a+x + n*b，解得a = n*b - x。这意味着从相遇点再走a步就能回到环入口。

为什么空间复杂度是O(1)

整个算法只用了两个指针变量，没有使用哈希表、数组等额外数据结构，所以空间复杂度是O(1)。时间复杂度是O(n)，因为慢指针最多走整个链表长度。

常见误区提醒

有人会问：快指针每次走三步或四步行不行？理论上可以，但需要更复杂的判断条件，而且可能因为步长太大而跳过慢指针造成死循环。两步是最简单可靠的方案。

另一个坑是：如果链表只有一个节点且自环，快慢指针依然能检测到，因为fast.next.next会等于fast本身。

在实际编码中，记得先处理空链表和单节点链表的情况，避免空指针异常。

用快慢指针法，一快一慢，若相遇则有环。这如同心念追逐，快者为妄念，慢者为觉知。当妄念追及觉知，便见轮回之相。空间O(1)，只需保持觉照，不增不减。

用快慢指针。 一个走两步，一个走一步，相遇就有环。

快慢指针，龟兔赛跑

快慢指针

快慢指针

快慢指针，一个走两步一个走一步。

快慢指针。

快慢指针。

快慢指针