如何检测链表是否存在环？

核心回答

可以使用快慢指针：两个指针都从头节点出发，slow 每轮走一步，fast 每轮走两步。移动后若指向同一个节点，说明有环；如果快指针或它的下一节点为空，则无环。

有环时，慢指针最终进入环中，此后快指针相对慢指针每轮前进一个节点，必然在有限轮内追上。时间复杂度是 O(n)，额外空间是 O(1)，其中 n 是从头节点能够到达的不同节点数。

比较的是节点身份，而不是节点值。两个不同节点即使都存了数字 1，也不代表形成环；判断过程中也不需要修改链表。

Python 实现

假设节点有 val 和 next 字段，输入链表在本次检查期间保持稳定。

def has_cycle(head) -> bool:
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

循环条件先确认 fast 和 fast.next 存在，再访问 fast.next.next。第三个节点可以为空，赋值给 fast 后，下一轮自然退出。

初始化时两个指针本来都指向头节点，所以先移动，再比较。否则任何非空链表都会被误判为有环。Python 的 is 比较对象身份，不受节点类自定义 __eq__ 的影响。

为什么不会一直错过？

无环时，沿着 next 只能不断向后，最终到达空节点，因此循环会结束。

有环时，设入环前有 a 个节点，环长为 L。慢指针进入环后，快指针也已经在环内；此后每轮两者之间的相对位置改变一格。沿环的距离只有 L 种余数，至多再经过 L 轮就会重合。因此总轮数是 O(a + L)，并不会无限绕下去。

这里按每轮结束时的位置比较。快指针一次走两步不影响结论，因为它相对每轮走一步的慢指针，净增加的距离仍然是一格。

边界情况

• 空链表： 循环不执行，返回 False。
• 单节点、next 为空： 无环。
• 单节点指向自己： 移动后两个指针仍在该节点，返回 True。
• 环入口是头节点或中间节点： 都可以检测，不要求尾节点一定回到头部。
• 多个节点值相同： 按对象身份判断，不会因为值重复而误报。

例如三个值都为 1 的节点，若最后指向空，仍然无环；若最后指回第二个节点，才形成从第二个节点开始的环。

常见追问

能不能用哈希集合？

可以。遍历时记录已经到达的节点身份，再次遇到同一个节点就有环，走到空则无环。使用合适哈希集合时，期望时间 O(n)、额外空间 O(n)。若节点类重写了相等和哈希规则，要确保集合记录的仍是节点身份；快慢指针则不需要保存这份集合。

相遇点就是环入口吗？

不一定。第一次相遇后，让一个指针回到头节点，另一个留在相遇点，二者都改成每次走一步，再相遇的位置才是入口。

设头部到入口距离为 a，入口到首次相遇点沿环距离为 b。由于快指针走过的总路程是慢指针的两倍，可以推出 a + b 是环长 L 的整数倍。相遇点再前进 a 步恰好到入口，从头出发前进 a 步也到入口，因此二者会在那里相遇。

怎么求环长？

确认有环后，固定首次相遇节点，让另一个指针沿 next 前进并计数，第一次回到该节点时的步数就是环长。检测入口和环长都可以继续保持 O(n) 时间、O(1) 额外空间。

参考资料