LeetCode 141：链表环 — 逐步可视化追踪

Source: Dev.to

问题描述

给定一个链表的头节点，判断链表中是否存在环。如果通过不断沿 next 指针前进能够再次到达某个节点，则存在环。

思路

使用 Floyd 环检测算法（也称为 “乌龟和兔子” 技巧）。两个指针以不同速度遍历链表：

• 慢指针 每次移动一步。
• 快指针 每次移动两步。

如果存在环，快指针最终会与慢指针相遇。若没有环，快指针会到达链表末尾（None）。

复杂度分析

• 时间复杂度: (O(n)) – 每个节点最多被访问常数次。
• 空间复杂度: (O(1)) – 只使用了两个指针，与链表大小无关。

参考实现（Python）

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False

        slow = head
        fast = head.next

        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next

        return True

交互式可视化

打开交互式可视化 – 使用 TraceLit（LeetCode 练习的可视化算法追踪器）逐行演示代码。