如何判断一个链表是否有环？

推荐答案

-- -------------------- ---- -------
----- ---------
    --- -------------- ---
        -------- - -
        --------- - ----

--- -------------- --------- -- -----
    -- --- ---- -- --- ----------
        ------ -----
    
    ---- - ----
    ---- - ---------
    
    ----- ---- -- -----
        -- --- ---- -- --- ----------
            ------ -----
        ---- - ---------
        ---- - --------------
    
    ------ ----

本题详细解读

1. 问题描述

判断一个链表是否有环，即链表中是否存在一个节点，通过连续跟踪 next 指针再次到达该节点。

2. 解题思路

使用快慢指针（Floyd's Tortoise and Hare Algorithm）来判断链表是否有环。快指针每次移动两步，慢指针每次移动一步。如果链表中有环，快指针最终会追上慢指针；如果没有环，快指针会到达链表末尾。

3. 代码解析

• ListNode 类：定义了链表节点的结构，包含 val 和 next 两个属性。
• hasCycle 函数：接受链表的头节点 head 作为参数，返回一个布尔值表示链表是否有环。
  • 边界条件：如果链表为空或只有一个节点，直接返回 False。
  • 初始化指针：slow 指针指向头节点，fast 指针指向头节点的下一个节点。
  • 循环判断：在 slow 和 fast 不相等的情况下，移动 slow 指针一步，fast 指针两步。如果 fast 或 fast.next 为 None，说明链表无环，返回 False。
  • 返回结果：如果 slow 和 fast 相等，说明链表有环，返回 True。

4. 复杂度分析

• 时间复杂度：O(n)，其中 n 是链表中节点的数量。最坏情况下，快指针和慢指针会遍历整个链表。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。