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

题目描述

给定一个链表的头节点 head，判断链表中是否存在环（即某个节点可以通过连续跟踪 next 指针再次到达）。如果链表中存在环，则返回 true；否则，返回 false。

这是一个经典问题，但我们将探讨两种主要解法：基于哈希集合的直观方法，以及更高效的 Floyd 判圈算法（快慢指针法），并分析它们如何结合哈希思想解决环检测问题。

解题过程

步骤1：理解链表环

• 链表节点定义（以常见编程语言为例）：

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

• 环示例：节点 A -> B -> C -> D -> E -> C（即 E 的 next 指向 C，形成环 C -> D -> E -> C）。
• 任务：检测链表中是否存在这样的环。

步骤2：基于哈希集合的解法

核心思路：遍历链表，将每个访问过的节点存入哈希集合。如果某个节点已经在集合中，说明链表有环（因为重复访问了节点）。

详细步骤：

1. 初始化一个空的哈希集合（例如 Python 的 set() 或 Java 的 HashSet），用于存储已访问的节点引用（内存地址）。
2. 从头节点 head 开始遍历链表：
   • 如果当前节点 node 为 None，说明到达链表末尾，无环，返回 false。
   • 检查 node 是否在哈希集合中：
     • 如果在，说明之前访问过此节点，链表有环，返回 true。
     • 如果不在，将 node 加入集合，并移动到下一个节点 node = node.next。
3. 遍历结束（无 None 中断）则返回 false（实际上不会发生，因为无环链表最终会到 None）。

复杂度分析：

• 时间复杂度：O(n)，最坏情况下遍历所有节点一次。
• 空间复杂度：O(n)，哈希集合存储最多 n 个节点。

代码示例（Python）：

def hasCycle_hash(head):
    visited = set()
    node = head
    while node:
        if node in visited:
            return True
        visited.add(node)
        node = node.next
    return False

步骤3：Floyd 判圈算法（快慢指针法）

核心思路：使用两个指针，一个慢指针每次移动一步，一个快指针每次移动两步。如果链表有环，快指针最终会追上慢指针（相遇）；如果无环，快指针会先到达末尾。

详细步骤：

1. 初始化两个指针：slow = head，fast = head。
2. 进入循环，条件是 fast 和 fast.next 均不为 None（确保快指针可以安全移动两步）：
   • 慢指针移动一步：slow = slow.next。
   • 快指针移动两步：fast = fast.next.next。
   • 检查 slow == fast：
     • 如果相等，说明两指针在环中相遇，链表有环，返回 true。
3. 循环结束（快指针遇到 None），说明链表无环，返回 false。

为什么有效：

• 如果有环，快指针每次比慢指针多走一步，相当于快指针以相对速度 1 步/次靠近慢指针，最终必然在环内相遇。
• 时间复杂度：O(n)，空间复杂度：O(1)，无需额外存储。

代码示例（Python）：

def hasCycle_floyd(head):
    if not head:
        return False
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

步骤4：哈希集合与Floyd算法的结合思考

虽然 Floyd 算法更优，但哈希集合方法在特定场景下有独特优势：

1. 可获取环的入口节点：哈希集合中第一个重复的节点就是环的起点（Floyd 算法需要额外步骤推导）。
2. 适用于更广义的“状态检测”：例如，在迭代函数或状态机中检测循环（如“快乐数”问题），哈希集合可记录所有访问过的状态。
3. 直观易懂：直接利用哈希集合的 O(1) 查找特性，逻辑简单。

结合应用示例：在“快乐数”问题中（判断一个数是否最终变为 1，或进入无限循环），我们使用哈希集合记录每次计算的结果，一旦重复则检测到循环——这正是哈希集合在状态环检测中的典型应用。

总结

• 哈希集合法：通用性强，可记录访问历史，直接检测重复，适合需要环入口或状态遍历的场景，但需要 O(n) 空间。
• Floyd 判圈算法：空间最优（O(1)），适合纯环检测且无需额外信息的场景。
• 选择依据：根据问题需求——如果只需判断是否存在环且追求空间效率，用 Floyd 算法；如果需要环的起点或处理状态序列，用哈希集合。

通过此题，你掌握了两种环检测方法，并理解了哈希结构在解决循环相关问题中的灵活应用。