141. 环形链表I（Linked List Cycle）

频次 ★★★★★ · 难度 🟢 · 高频：全厂

题目

判断链表中是否存在环。

示例：

输入: 3 -> 2 -> 0 -> -4 -> (指回 2)
输出: true

思路

Floyd 判圈（快慢指针）：慢指针每次走一步，快指针每次走两步。如果链表有环，快指针迟早会在环内追上慢指针；如果没有环，快指针会先到达链表尾部（null）。

代码

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

复杂度

• 时间：O(n) — 有环时快指针最多在环内多绕一圈就能追上慢指针
• 空间：O(1) — 不需要额外的哈希集合记录访问过的节点

边界条件

• 空链表：fast == null，循环不执行，返回 false。
• 只有一个节点且不自环：fast.next == null，循环不执行，返回 false。
• 只有一个节点且自环（head.next == head）：第一次循环 slow 和 fast 都停在 head，立即相遇，返回 true。

变式

• 如果还需要找到环的入口节点，见 142. 环形链表 II。
• 如果允许 O(n) 额外空间：用 HashSet 记录访问过的节点，遍历时如果遇到已经访问过的节点就说明有环，思路更直观但空间开销更大。

易错点

• 循环条件必须同时检查 fast != null && fast.next != null，只检查其中一个在链表长度为偶数时会造成空指针异常（因为 fast 每次走两步，可能跳过 null 检查直接访问 fast.next.next）。
• 判断相遇要用 slow == fast（引用相等），不能用值相等，链表中可能有重复的值。

面试追问

• 为什么快指针每次走 2 步、慢指针走 1 步就一定能相遇，而不是永远追不上？ 如果有环，一旦两个指针都进入环内，它们之间的相对速度差是 1（每一步快指针比慢指针多走 1 步），相当于在环上”追及问题”，环的长度有限，所以经过最多”环长”步一定会追上；如果没有环，快指针会正常走到链表尾部（null），不会死循环。
• 能不能不用额外指针，只用一个指针加计数来判断？ 不行，单指针无法区分”链表很长但没有环”和”链表有环、指针一直在环里转圈”这两种情况，必须借助双指针的相对速度差，或者用额外空间记录访问过的节点。

关联题

• 同套路：142. 环形链表II、876. 链表的中间结点 —— 快慢指针三兄弟：判环、找入口、找中点
• 进阶：202. 快乐数 —— 数字平方和序列判环，Floyd 思想脱离链表也能用
• 易混：160. 相交链表 —— 同是”双指针相遇”，但靠换轨对齐路程差，不是速度差
• 知识点：环检测与 JVM 引用计数无法回收循环引用，是同一个”引用成环”问题