141 & 142. 环形链表

141. 环形链表

题目链接（简单）

题目描述

给你一个链表的头节点 head，判断链表中是否有环。

如果链表中存在环，则返回 true；否则，返回 false。

数据范围：

链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5

方法一：哈希集合

思路及解法

遍历链表，用哈希集合记录访问过的节点。遍历过程中：

若当前节点已在集合中，说明绕回了，返回 True；
否则加入集合，继续往下；
走到 None，说明无环，返回 False。

时间 $O(n)$，空间 $O(n)$。

代码

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

复杂度分析

时间复杂度：$O(n)$，每个节点最多访问一次。
空间复杂度：$O(n)$，哈希集合存储所有节点。

方法二：快慢指针（Floyd 判圈）

思路及解法

慢指针 slow 每次走 1 步，快指针 fast 每次走 2 步，都从 head 出发：

若链表无环，fast 会先到达 None，返回 False；
若链表有环，fast 一定会在环内追上 slow，两者相遇，返回 True。

时间 $O(n)$，空间 $O(1)$。

LC 141 与 LC 142 的区别：本题只需判断「有没有环」，起点怎么设都行；LC 142 还要找「入环点」，必须让两者从同一起点出发，数学推导才成立。

代码

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

复杂度分析

时间复杂度：$O(n)$。
空间复杂度：$O(1)$，只用两个指针。

142. 环形链表 II

题目链接（中等）

题目描述

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

不允许修改链表。

数据范围：

链表中节点的数目范围在 [0, 10^4] 内
-10^5 <= Node.val <= 10^5

进阶：你是否可以使用 $O(1)$ 空间解决此题？

方法一：哈希表

思路及解法

最直观的做法：从头遍历链表，把每个访问过的节点存进哈希集合。遍历过程中：

如果当前节点已经在集合里，说明之前访问过，这个节点就是入环点，直接返回；
否则把当前节点加入集合，继续往下走；
走到 null 说明没有环，返回 None。

为什么入环点会被第一个重复访问？

从链表头出发一路走，在环外的节点都只会被访问一次；一旦进入环，绕一圈后一定会再次遇到入环点——这是第一个「重复访问」的节点。

代码

class Solution:
    def detectCycle(self, head: ListNode | None) -> ListNode | None:
        visited = set()
        while head:
            if head in visited:
                return head
            visited.add(head)
            head = head.next
        return None

复杂度分析

时间复杂度：$O(n)$，每个节点最多访问一次。
空间复杂度：$O(n)$，哈希集合存储所有节点。

方法二：快慢指针（Floyd 判圈）

思路及解法

第一步：判断是否有环。

用两个指针 slow 和 fast，都从 head 出发：

slow 每次走 1 步；
fast 每次走 2 步。

如果链表无环，fast 会先到达 None，直接返回 None。
如果链表有环，fast 一定会在环内追上 slow，两者相遇。

第二步：找到入环点。

|318

设：

$a$ = 链表头到入环点的距离；
$b$ = 入环点到相遇点的距离；
$c$ = 相遇点到入环点的距离（沿环再走一圈回到入环点）。

相遇时：

slow 走了 $a + b$；
fast 走了 $a + b + n(b + c)$，其中 $n \ge 1$ 是 fast 比 slow 多绕的整圈数。

因为 fast 速度是 slow 的两倍：

[
a + b + n(b + c) = 2(a + b)
]

化简：

[
a = c + (n - 1)(b + c)
]

这个等式的含义是：从链表头走到入环点的距离 $a$，等于从相遇点再走 $c$，加上 $n-1$ 圈环长。

因此，让一个指针 ptr 从 head 出发，slow 从相遇点出发，两者每次都走 1 步，它们一定会在入环点相遇。

直觉理解：相遇后，让「从头出发」和「从相遇点出发」两个指针同速前进，它们第一次相遇的位置就是入环点。

为什么必须让 slow 和 fast 从同一起点出发？

因为上面的推导依赖于「相遇时 fast 走的距离恰好是 slow 的两倍」。若 fast 一开始就多走 1 步，等式会变成 $a = c + (n-1)(b+c) - 1$，入环点会偏移 1 位，找不到正确答案。

相比之下，LC 141 只判断「有没有环」，不依赖这个等式，所以起点怎么设都行。

代码

class Solution:
    def detectCycle(self, head: ListNode | None) -> ListNode | None:
        slow = fast = head

        # 第一步：快慢指针判断是否有环
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                # 第二步：找入环点
                ptr = head
                while ptr != slow:
                    ptr = ptr.next
                    slow = slow.next
                return ptr

        return None

复杂度分析

时间复杂度：$O(n)$，判断环的遍历不超过链表长度，找入环点的遍历也不超过链表长度。
空间复杂度：$O(1)$，只用两个指针。

两种方法对比

方法	时间	空间	是否满足进阶	特点
哈希表	$O(n)$	$O(n)$	❌	思路最直观，代码最简
快慢指针	$O(n)$	$O(1)$	✅	进阶解法，需推导

总结

141 与 142 的区别：
- 141 只判断有无环，快慢指针起点随意；
- 142 要找入环点，快慢指针必须从同一起点出发。
哈希表法：遍历时记录访问过的节点，第一个重复出现的节点就是入环点；
快慢指针法：
1. slow 每次 1 步，fast 每次 2 步，若相遇则有环；
2. 相遇后让 ptr 从头部出发，与 slow 同速前进，相遇点即入环点；
关键公式：$a = c + (n-1)(b+c)$，说明「从头到入环点」=「从相遇点绕若干圈到入环点」；
核心记忆：快慢相遇 → 一个从头、一个从相遇点，同速走，相遇即入环点。

141 & 142. 环形链表

141. 环形链表

题目描述

方法一：哈希集合

思路及解法

代码

复杂度分析

方法二：快慢指针（Floyd 判圈）

思路及解法

代码

复杂度分析

142. 环形链表 II

题目描述

方法一：哈希表

思路及解法

代码

复杂度分析

方法二：快慢指针（Floyd 判圈）

思路及解法

代码

复杂度分析

两种方法对比

总结

相关题目