如何在Python中快速检测链表结构中是否存在环？-Python教程-PHP中文网

不能用集合记录遍历节点因空间复杂度为o(n)，不满足o(1)要求，且自定义__eq__/__hash__或节点重用可能导致误判；快慢指针法需初始化fast=head.next并每次检查fast和fast.next非空。

如何在python中快速检测链表结构中是否存在环？

为什么不能用集合记录遍历过的节点

用 set 存每个 node 然后每次查是否重复，确实能工作，但会额外占用 O(n) 空间。实际面试或嵌入式场景中，常被明确要求「空间复杂度 O(1)」——这时候就得放弃哈希表思路。

更隐蔽的坑是：如果链表节点自定义了 __eq__ 或 __hash__，而你没控制好逻辑，set 查找可能出错；或者节点对象被重用（比如测试用例反复构造），哈希值冲突也会埋雷。

快慢指针法怎么写才不出错

核心是让一个指针走 1 步（slow），另一个走 2 步（fast）。只要存在环，fast 必然在某轮追上 slow；若 fast 先走到 None，说明无环。

必须先判 fast 和 fast.next 是否为 None，否则 fast.next.next 会抛 AttributeError
初始化时，slow = head，fast = head.next（不是 head），否则循环一开始就会判定相等（哪怕无环）
循环条件用 while fast and fast.next:，比 while fast is not None 更安全

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

环的起点和长度还能顺便算出来吗

能，但别在基础检测里硬塞——它会让逻辑变重、易错，且多数场景只关心「有没有」。

python-script-generator

快速生成专业的 Python 脚本和应用代码。一键创建完整项目结构，支持CLI、API、爬虫、Bot、Django等多种项目类型，包含完整的项目结构、配置文件、依赖管理、测试、README和文档。

下载

如果真需要起点：等快慢指针相遇后，把 slow 拉回 head，两个指针都每次走 1 步，再次相遇点就是环入口；环长度则从该点出发再走一圈计数。

注意：这些操作的前提是确认已有环。如果跳过基础检测直接跑起点算法，遇到无环链表会无限循环。

Python 中节点定义不统一怎么办

LeetCode 用的是 ListNode(val, next)，但自己写的类可能没 next 属性，或叫 next_node；有的甚至用字典模拟节点（{'val': 1, 'next': ...}）。

检测函数必须适配实际结构：

检查属性名：用 hasattr(node, 'next') 或 getattr(node, 'next', None) 替代硬写 node.next
避免直接比较 node1 == node2 —— 如果节点没实现 __eq__，这会比较内存地址；应改用 is（即 slow is fast）
空节点判断别用 if node == None，统一用 if node is None