在刷题和面试的过程中，链表（Linked List）绝对是一个绕不开的经典数据结构。今天我们要聊的是一个非常高频且有趣的面试题：如何判断一个单向链表里是否存在环？

这个问题如果用常规的“哈希表”来做，把走过的节点都存起来，每次走一步就查一下，虽然能解决，但在空间上需要消耗额外的内存。那么，有没有一种不需要额外空间、极其优雅的解法呢？

答案是肯定的，那就是大名鼎鼎的快慢指针法（Fast and Slow Pointers），也被称为“龟兔赛跑算法”（Floyd’s Tortoise and Hare Algorithm）。

核心思想：操场上的“套圈”游戏

在讲解冷冰冰的代码之前，我们先想象一个生活场景：想象一下，有两个人在操场上跑步，一个是飞毛腿（快指针），一个是慢吞吞的散步者（慢指针）。

情况一： 如果跑道是一条直线（链表没有环），那么飞毛腿很快就会跑到终点，两人永远不会再次相遇。

情况二： 如果跑道是一个环形操场（链表有环），因为飞毛腿跑得快，他迟早会在操场里多跑一圈，然后从后面追上甚至“套圈”散步者。只要两人在跑道上相遇，就说明跑道一定是环形的！

这就是快慢指针法的全部奥秘：让两个指针以不同的速度在链表里移动，如果它们相遇了，说明有环；如果快指针走到了尽头（null），说明没环。

代码实现

下面这段 Java 代码就是这段逻辑的完美实现，非常简练：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public boolean hasCycle(ListNode head) {
    // 1. 边界情况处理：如果链表为空，或者只有一个节点且没有指向自己，肯定无环
    if (head == null || head.next == null) return false;
    
    // 2. 初始化快慢指针
    ListNode slow = head;        // 慢指针，初始在起点
    ListNode fast = head.next;   // 快指针，初始在起点的下一步
    
    // 3. 开始“追击”循环
    while (slow != fast) {
        // 如果快指针碰到了尽头，说明前面没有路了，也就是没有环
        if (fast == null || fast.next == null) {
            return false;
        }
        // 慢指针每次走一步
        slow = slow.next;
        // 快指针每次走两步
        fast = fast.next.next;
    }
    
    // 4. 循环结束的唯一条件是 slow == fast，也就是两人相遇了，说明有环！
    return true;
}

虽然代码很短，但有几个精妙的小细节值得我们深入品味：

1、为什么 fast 初始在 head.next 而不是 head？ 在这段特定的代码中，while 循环的条件是 slow != fast。如果一开始把它们都设为 head，循环一开始就不成立，直接跳出了。为了让循环能正常跑起来，我们让快指针先“抢跑”一步。

2、为什么只判断 fast 和 fast.next 为不为空？ 因为快指针跑得快，它永远冲在最前面。如果链表走到头了，肯定是快指针先发现的。快指针一次要走两步（fast.next.next），所以必须保证它当前的位置和下一个位置都不是 null，否则就会报空指针异常（NullPointerException）。