0141.环形链表

难度：🟢 简单

标签：哈希表、链表、双指针

链接：141. 环形链表

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

解题思路

核心思想

本题的核心思想是 “龟兔赛跑”。我们可以想象两个指针在链表上移动，一个跑得快（快指针），一个跑得慢（慢指针）。如果链表存在一个环（就像一个圆形跑道），那么快指针最终一定会从后面追上并与慢指针相遇。如果链表没有环（一条直线跑道），那么快指针将永远在慢指针前面，直到它到达终点（null）。

思路选择

快慢指针法（Floyd's Tortoise and Hare algorithm） 是解决此问题的最经典、最高效的思路。

• 慢指针 (slow)：每次移动一步。

• 快指针 (fast)：每次移动两步。

通过这种速度差，我们来判断是否存在相遇点。

关键步骤

1. 处理边界情况：如果链表为空 (head === null) 或只有一个节点 (head.next === null)，则不可能形成环，直接返回 false。

2. 初始化指针：创建两个指针 slow 和 fast，都让它们从头节点 head 开始。

3. 开始追逐：启动一个循环，循环的条件是 fast 指针以及 fast 的下一个节点都不能为 null（确保快指针移动两步时不会出错）。

4. 移动指针：在循环内部，slow 指针向前移动一步，fast 指针向前移动两步。

5. 判断相遇：每次移动后，立即判断 slow 和 fast 是否指向同一个节点 (slow === fast)。

   • 如果相遇，说明存在环，立即返回 true。

6. 循环结束：如果循环正常结束（即 fast 到达了链表末尾），则说明没有环，返回 false。

代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 * this.val = val;
 * this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
    // 初始化快慢指针
    let 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) 其中 n 是链表的节点总数。在无环的情况下，快指针遍历整个链表。在有环的情况下，指针相遇前走过的路程也与链表长度成正比。

• 空间复杂度：O(1) 我们只使用了 slow 和 fast 两个额外的指针，所以空间消耗是恒定的。

相关题目

• 0142.环形链表 II
• 0287.寻找重复数

总结

本题是快慢指针技巧在链表问题中的一个标志性应用。这种方法不仅空间效率极高，而且逻辑优雅，是处理链表环问题的首选方案。理解“龟兔赛跑”的模型可以帮助我们轻松地解决这类问题。