算法 - 判断链表是否有环 (Linked List Cycle)

Posted on

1. 题目

给定一个链表头节点 head，判断链表中是否存在环。若存在环返回 true，否则返回 false。

进阶：你能用 O(1)（即常量）内存解决此问题吗？

示例:

1
2
3
4
5
6
7
8
输入: head = [3, 2, 0, -4]，且尾节点连回索引 1 的节点
输出: true（存在环）

输入: head = [1, 2]，2 -> 1 成环
输出: true

输入: head = [1]，无环
输出: false

节点定义：

1
2
3
4
5
6
7
8
class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0;
        this.next = next ?? null;
    }
}

2. 解题思路

2.1 哈希集合（直观）

遍历链表，把访问过的节点存进 Set。若再次遇到已在集合里的节点，说明成环。

  • 时间 O(n)，空间 O(n)。缺点：不满足「常量内存」。

2.2 快慢指针（Floyd 判圈，最优）

想象跑道：快的和慢的在一个环形跑道上一定会相遇。

  • slow 每次走 1 步，fast 每次走 2 步，都从 head 出发。

  • 若有环，fast 最终会从后面追上 slow，两者相遇 → 返回 true。

  • 若无环，fast（或 fast.next）会先到 null → 返回 false。

  • 时间复杂度：O(n)。

  • 空间复杂度：O(1)，只用两个指针。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function hasCycle(head: ListNode | null): boolean {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow!.next;           // 走一步
        fast = fast.next.next;       // 走两步

        if (slow === fast) return true; // 相遇即有环
    }

    return false; // fast 到头，无环
}

// 测试：构造 3 -> 2 -> 0 -> -4 -> (回到 2)
const n = new ListNode(3, new ListNode(2, new ListNode(0, new ListNode(-4))));
n.next.next.next.next = n.next; // 造环
console.log(hasCycle(n)); // true
console.log(hasCycle(new ListNode(1))); // false

4. 面试延伸

  • 为什么快指针不能走 3 步？ 走 2 步能保证追上；步长差为 1 时相遇最有保证，是经典设定。
  • 求环入口节点 是本题的孪生题（LeetCode 142），见下一篇 [寻找环形链表入口节点]。
  • 快慢指针的通用套路还能解：链表中点、判断回文链表、数组找重复数（287） 等「成环」问题。
  • 边界：fast && fast.next 的判空顺序不能反，否则访问 fast.next.next 会空指针。

难度：简单 | LeetCode 141 题 | 快慢指针代表作