环形链表 图解题解

这道题真正在问什么

给一条单链表，判断其中是否存在环——即某个节点的 next 指回了前面出现过的节点。有环的链表沿 next 一直走永远到不了 null，朴素的「走到头就没环」会陷进死循环，所以问题的实质是：如何在有限步内区分「还没走到头」和「永远走不到头」。

为什么记录访问过的节点还不够好

最直觉的解法是用哈希表存下每个走过的节点：再次遇到已存在的节点说明兜了圈，有环；走到 null 说明无环。时间 O(n)，思路也干净，但要 O(n) 的额外空间。题目的进阶要求是 O(1) 空间——链表可能极长，这个内存开销值得省，也正是这个约束把快慢指针逼了出来。

为什么快慢指针有环时一定会相遇

让 slow 每次走 1 步、fast 每次走 2 步，同时从头出发。无环时 fast 在前面开路，先撞到 null，循环结束返回 false，不存在漏判。

有环时，fast 先进环，slow 随后也进环。从此两者都在环上转圈，用相对运动看最清楚：fast 相对 slow 每一轮净逼近 1 步。两者的环上距离是一个严格递减的非负整数，每轮减一、不可能被跳过，减到 0 的那一刻两指针落在同一个节点上——这就是「相遇」。所以有环必相遇、无环必到 null，两种结局覆盖所有情况，算法一定终止。

这也回答了「为什么 fast 走 2 步而不是 3 步」：步差为 1 保证距离逐格递减、不会隔着跨过去；步差更大时逼近过程可能反复错过，正确性论证会复杂得多。2 步是让证明最简单的选择。

循环条件为什么要同时判 fast 和 fast.next

fast 一次要跨两步，即先取 fast.next 再取它的 next。若只检查 fast 非空，当 fast 停在尾节点时 fast.next 是 null，再取一层 next 就是空指针崩溃。所以循环条件必须是 fast 和 fast.next 都非空，这同时天然处理了空链表和单节点无环链表——循环体一次都不进，直接返回 false。

另一个细节是相遇判断用节点身份（是不是同一个对象）而不是节点值，链表里完全可能有多个值相同的不同节点。

复杂度怎么数，相关的进阶题

时间 O(n)：slow 进环之前最多走链长步；进环后 fast 与 slow 的距离不超过环长，每轮缩 1，最多再走环长步就相遇，总步数是线性的。空间 O(1)：自始至终只有两个指针。

这套 Floyd 判圈还有一个漂亮的续集：LeetCode 142 要求找出环的入口。做法是相遇后把一个指针放回头节点，两个指针改为同速各走 1 步，再次相遇的位置就是环入口——背后是「头到入口的距离等于相遇点沿环走到入口的距离」这条等式。判环是那道题的前置零件，本题吃透了，142 只差一步数学。

Python

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next        # 慢走 1 步
        fast = fast.next.next    # 快走 2 步
        if slow is fast:        # 相遇 = 有环
            return True
    return False                 # fast 到 null = 无环

C++

bool hasCycle(ListNode* head){
    ListNode *slow = head, *fast = head;
    while(fast && fast->next){
        slow = slow->next;          // 慢 1 步
        fast = fast->next->next;    // 快 2 步
        if(slow == fast) return true;
    }
    return false;
}

Java

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