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

题目描述
给定一个链表的头节点 head，判断链表中是否存在环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达，则链表中存在环。要求实现一个函数，如果链表中存在环则返回 true，否则返回 false。

示例

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

注意：pos 在输入中不给出，仅用于表示链表中节点形成环的连接位置。

解题思路
有两种常见方法：

1. 哈希集合法：遍历链表，用哈希集合记录已访问的节点，如果遇到重复节点说明有环。
2. 快慢指针法（Floyd判圈算法）：用两个指针，慢指针每次走一步，快指针每次走两步，如果相遇则有环。

本题要求结合哈希算法，因此重点讲解哈希集合法。快慢指针法可作对比。

详细解题步骤

步骤1：理解链表结构和环的定义
链表节点定义通常为：

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

环的存在意味着从某个节点出发，沿着 next 指针会回到一个之前访问过的节点。

步骤2：哈希集合法的核心思想
哈希集合（在Python中是 set，在Java中是 HashSet）能存储节点对象并支持 O(1) 时间的查找和插入。遍历链表时：

• 将每个节点存入哈希集合。
• 如果当前节点已在集合中，说明遇到了环的起点，返回 true。
• 如果遍历到 None（链表尾部），说明无环，返回 false。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：O(n)，最坏情况存储所有节点。

步骤3：算法步骤分解

1. 初始化一个空的哈希集合 visited。
2. 用指针 cur 指向头节点 head。
3. 循环遍历链表，条件为 cur 不为 None：
   • 如果 cur 在 visited 中，返回 true。
   • 否则，将 cur 加入 visited，cur 移动到 cur.next。
4. 循环结束（即 cur 为 None），返回 false。

步骤4：图解示例
以 head = [3,2,0,-4] 且 -4.next = 2 为例：

1. 遍历顺序：3 → 2 → 0 → -4 → 2（再次遇到 2）。
2. 哈希集合变化：
   • 访问 3：集合 {3}
   • 访问 2：集合 {3, 2}
   • 访问 0：集合 {3, 2, 0}
   • 访问 -4：集合 {3, 2, 0, -4}
   • 再次访问 2：发现 2 已在集合中 → 检测到环，返回 true。

步骤5：代码实现

def hasCycle(head):
    visited = set()  # 哈希集合存储已访问节点
    cur = head
    while cur:
        if cur in visited:
            return True
        visited.add(cur)
        cur = cur.next
    return False

步骤6：边界情况处理

• 空链表（head 为 None）：直接返回 false。
• 单节点成环：head.next == head，第一次遍历时节点不在集合，加入后第二次遇到时检测到环。
• 大链表无环：遍历直到 None 返回 false。

步骤7：与快慢指针法对比

• 哈希集合法直观易懂，但需 O(n) 额外空间。
• 快慢指针法（Floyd判圈算法）空间复杂度 O(1)，但稍难理解。
  适用场景：
  • 内存充足时，哈希法代码简单。
  • 内存受限时，用快慢指针。

步骤8：进阶思考
如果要求返回环的入口节点（而不只是判断是否有环），哈希集合法可轻松扩展：遇到重复节点时直接返回该节点。快慢指针法需额外步骤找到入口。

总结
本题展示了哈希集合在检测重复访问节点时的经典应用。核心是哈希集合的 O(1) 查找能力，使得算法在 O(n) 时间内完成环检测。实际面试中可根据需求在哈希法和快慢指针法中选择。