Skip to main content

环形链表

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

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

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

示例 1：

image

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

image

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

image

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

简单做法：迭代给遍历到的每个节点添加顺序，若下次遍历发现存在顺序的节点则存在环

进阶做法：要判断单链表中是否存在环，最经典且高效的方法是快慢指针法（弗洛伊德龟兔赛跑算法），该方法能在 O(n) 时间复杂度和 O(1) 空间复杂度内解决问题。

核心思路​

  1. 定义指针：设置两个指针 slow（慢指针）和 fast（快指针），初始时均指向头节点 head。
  2. 移动规则：
    • 慢指针每次向后移动 1 步；
    • 快指针每次向后移动 2 步。
  3. 判断逻辑：
    • 若链表无环：快指针会先到达链表末尾（fast 或 fast.next 为 null），此时返回 false。
    • 若链表有环：快指针会在环内追上慢指针（slow === fast），此时返回 true。

原理证明​

  • 若链表有环，快慢指针最终一定会相遇：
    当慢指针进入环时，快指针已在环内。设环的长度为 L，此时快慢指针的距离为 d（d < L）。由于快指针速度是慢指针的 2 倍，每移动一次，两者距离减少 1（d = d - (2-1) = d-1），最终会在 d 步后相遇。

代码实现​

function hasCycle(head) {
    if (!head || !head.next) return false; // 空链表或单节点无环
    
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) { // 快指针未到达末尾
        slow = slow.next;       // 慢指针走1步
        fast = fast.next.next;  // 快指针走2步
        
        if (slow === fast) {    // 相遇，存在环
            return true;
        }
    }
    
    return false; // 快指针到达末尾，无环
}

复杂度分析​

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

    • 无环情况：快指针最多移动 n/2 步（到达末尾）。
    • 有环情况：慢指针进入环后，快指针最多移动 2L 步（L 为环长）即可追上，总步数仍为 O(n)。

  • 空间复杂度：O(1)。仅使用两个指针，无需额外空间。

边界情况验证​

  • 空链表（head = null）：返回 false。
  • 单节点链表（head.next = null）：返回 false。
  • 有环链表（如 1 → 2 → 3 → 2）：快慢指针会在环内相遇，返回 true。

与其他方法对比​

方法时间复杂度空间复杂度特点
快慢指针法O(n)O(1)最优解，无额外空间
哈希表记录法O(n)O(n)记录访问过的节点，空间开销大

快慢指针法通过“速度差”巧妙利用环的特性，无需额外空间即可判断环的存在，是解决该问题的标准解法。