使用哈希集合检测循环链表（Floyd判圈算法与哈希表结合）

题目描述

给定一个链表的头节点 head，判断链表中是否存在环（循环链表）。即，链表中的某个节点的 next 指针指向了其自身或链表中其之前的某个节点，使得遍历过程可以无限进行。

要求：实现一个函数，如果链表中存在环，则返回 true；否则，返回 false。

进阶：尝试在不使用额外空间（O(1) 空间复杂度）的情况下解决此问题，这通常通过 Floyd 判圈算法（又称龟兔赛跑算法）实现。本题目将结合哈希表（集合）的方法和 Floyd 判圈算法进行讲解，以展示不同思路。

解题过程循序渐进讲解

步骤 1：理解问题与输入输出

• 输入：一个链表的头节点 head，其定义通常如下（以常见语言伪代码描述）：

  class ListNode:
      def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
  

  节点值 val 在本题中不重要，关键是 next 指针。
• 输出：布尔值 true 或 false，表示是否存在环。

关键点：如果链表无环，遍历会以 None（或 null）结束；如果有环，遍历会无限循环，永远遇不到 None。

步骤 2：最直观的哈希表（集合）解法

哈希集合（HashSet）的核心作用是记录已经访问过的节点，利用其 O(1) 的查找和插入时间复杂度。

1. 算法思路：

   • 从链表头开始，逐个遍历每个节点。
   • 在遍历每个节点时，先检查这个节点是否已经存在于哈希集合中。
   • 如果存在，说明我们又回到了一个之前访问过的节点，链表有环，返回 true。
   • 如果不存在，则将此节点加入哈希集合，然后继续移动到下一个节点。
   • 如果遍历到 None（链表尾部），说明链表无环，返回 false。

2. 具体步骤：

   • 初始化一个空的哈希集合 visited。
   • 令指针 current 指向头节点 head。
   • 循环条件：当 current 不是 None 时：
     a. 检查 current 是否在 visited 中：
     • 如果在，返回 true。
       b. 将 current 加入 visited。
       c. 将 current 移动到 current.next。
   • 循环结束后，说明遇到了 None，返回 false。

3. 时间复杂度与空间复杂度：

   • 时间复杂度：O(n)，其中 n 是链表中的节点数。每个节点至多被访问一次。
   • 空间复杂度：O(n)，最坏情况下（无环链表），哈希集合需要存储所有 n 个节点。

步骤 3：深入理解 Floyd 判圈算法（龟兔赛跑算法）

这是一个使用 O(1) 额外空间的经典算法。它通过两个以不同速度移动的指针来检测环。

1. 核心思想：

   • 使用两个指针，一个称为“慢指针”（slow，通常每次移动一步），一个称为“快指针”（fast，通常每次移动两步）。
   • 如果链表中不存在环，快指针会先到达链表尾部（遇到 None）。
   • 如果链表中存在环，由于快指针每次比慢指针多走一步，在环内快指针最终会从后面追上慢指针（相遇）。这就像两个人在环形跑道上赛跑，跑得快的人最终会套圈追上跑得慢的人。

2. 算法步骤：

   • 初始化：slow = head，fast = head。
   • 循环条件：只要 fast 不为 None 且 fast.next 不为 None（确保可以安全地移动两步）：
     a. 慢指针移动一步：slow = slow.next。
     b. 快指针移动两步：fast = fast.next.next。
     c. 检查：如果 slow == fast，则两个指针相遇，说明有环，返回 true。
   • 循环结束后（即 fast 为 None 或 fast.next 为 None），说明快指针走到了链表末尾，链表无环，返回 false。

3. 为什么是安全的？

   • 如果无环，快指针会先到达末尾，循环结束。
   • 如果有环，假设环外有 a 个节点，环内有 b 个节点。当 slow 刚进入环时，fast 已经在环内。由于 fast 每次比 slow 多走一步，它们之间的距离（在环上的节点数差）每次减少 1，最终会在某个点（距离为 0）相遇。数学上可以证明，在 slow 走完环的第一圈之前，两者就会相遇。

4. 时间复杂度与空间复杂度：

   • 时间复杂度：O(n)。即使有环，slow 在相遇前走的步数不会超过链表总节点数 n。
   • 空间复杂度：O(1)，只用了两个指针变量。

步骤 4：比较两种方法

• 哈希表法：

  • 优点：直观，易于理解和实现。
  • 缺点：需要 O(n) 的额外空间存储节点引用。

• Floyd 判圈算法：

  • 优点：只需要 O(1) 的额外空间，是解决“检测环”问题的经典算法。
  • 缺点：理解其正确性需要一些推理，不如哈希表法直观。

步骤 5：代码实现示例（Python）

这里将两种方法都给出，以便对比。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # 方法一：哈希集合法
    def hasCycleHashSet(self, head: ListNode) -> bool:
        visited = set()
        current = head
        while current:
            if current in visited:
                return True
            visited.add(current)
            current = current.next
        return False

    # 方法二：Floyd 判圈算法
    def hasCycleFloyd(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False
        slow = head
        fast = head
        # 循环条件确保 fast 可以安全地移动两步
        while fast and fast.next:
            slow = slow.next      # 慢指针走一步
            fast = fast.next.next # 快指针走两步
            if slow == fast:      # 相遇，有环
                return True
        return False              # 快指针走到头了，无环

步骤 6：总结与扩展

• 本题是链表和哈希表结合的经典问题。哈希表法是一种通用的、用于检测重复访问的“足迹”方法。
• Floyd 判圈算法是解决“检测循环”和“寻找循环入口”问题的基石。在检测到环后，该算法还可以扩展用来找到环的起始节点（方法是：在相遇后，将一个指针重置到头节点，然后两个指针都以每次一步的速度前进，再次相遇的节点就是环的入口）。
• 在实际面试或问题解决中，如果空间复杂度没有严格限制，哈希表法因其简单性通常是首选。如果要求 O(1) 空间，则必须使用 Floyd 判圈算法。

通过以上步骤，你应该能清晰地理解如何使用哈希集合检测循环链表，以及它与更优空间复杂度算法（Floyd判圈）的关系与区别。