🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

       <<Git>><<MySQL>>

🌟心向往之行必能至

问题描述

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

环形链表的定义：链表中存在某个节点，可以通过连续跟踪 next 指针再次到达该节点。

核心思路：快慢指针法（龟兔赛跑算法）

这道题最经典的解法是快慢指针法，也叫 Floyd 判圈算法：

• 定义两个指针：slow（慢指针）和 fast（快指针）
• slow 每次走 1 步，fast 每次走 2 步
• 如果链表存在环，fast 最终会和 slow 在环中相遇；如果不存在环，fast 会先到达链表末尾

为什么快慢指针一定能相遇？

• 当 fast 进入环后，它和 slow 的距离会以每次 1 步 的速度缩小（因为 fast 比 slow 多走 1 步）
• 最终距离会缩小为 0，两个指针必然相遇
• 不存在 “永远追不上” 的情况，因为步长差为 1，是最小正整数

代码实现

cpp

运行

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 边界处理：空链表或只有一个节点的链表不可能有环
        if (head == NULL || head->next == NULL) {
            return false;
        }
        
        ListNode* slow = head;
        ListNode* fast = head;
        
        // 循环条件：fast 能继续走两步（避免空指针访问）
        while (fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;          // 慢指针走 1 步
            fast = fast->next->next;    // 快指针走 2 步
            
            // 相遇说明存在环
            if (slow == fast) {
                return true;
            }
        }
        
        // fast 走到末尾，说明无环
        return false;
    }
};

代码细节解析

1. 边界判断：
   • 空链表（head == NULL）或只有一个节点（head->next == NULL）的链表不可能形成环，直接返回 false
2. 指针初始化：
   • slow 和 fast 都从 head 出发，保证遍历起点一致
3. 循环条件：
   • fast->next != NULL && fast->next->next != NULL：避免 fast 访问空指针，确保 fast 可以安全走两步
4. 相遇判断：
   • 当 slow == fast 时，说明两个指针在环中相遇，直接返回 true
5. 循环结束：
   • 如果 fast 或 fast->next 为 NULL，说明链表有终点，不存在环，返回 false

复杂度分析

• 时间复杂度：O(n)
  • 无环时：fast 遍历到末尾，最多走 n/2 步
  • 有环时：fast 和 slow 相遇前最多走 n 步
• 空间复杂度：O(1)
  • 只使用了两个指针变量，没有额外开辟空间

其他解法对比

哈希表法

• 思路：遍历链表，用哈希表记录每个节点的访问情况，若再次访问到已存在的节点，则说明有环
• 优点：直观易懂
• 缺点：空间复杂度 O (n)，不如快慢指针法高效

cpp

运行

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> visited;
        while (head != NULL) {
            if (visited.count(head)) {
                return true;
            }
            visited.insert(head);
            head = head->next;
        }
        return false;
    }
};

总结

• 快慢指针法是环形链表问题的最优解，时间和空间复杂度都达到了最优
• 核心思想是利用 “不同步长的指针最终会在环中相遇” 的原理，避免了额外空间开销
• 代码简洁高效，是链表类问题的经典模板