141. 环形链表 (Easy)
专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/linked-list-cycle/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个链表的头节点 head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。
如果链表中存在环，返回 true；否则返回 false。
示例：
- 输入：head = [3,2,0,-4], pos = 1
- 输出：true（尾节点连接到索引为 1 的节点）
题目详细分析
- 数据范围： 链表中节点数在 [0, 10^4] 范围内，节点值在 [-10^5, 10^5] 范围内
- 输入特征： 单链表，每个节点只有 next 指针。可能有环，也可能无环
- 核心约束： 只能使用 O(1) 的额外空间（进阶要求），不能使用哈希表记录访问过的节点
- 隐藏条件： 环的形成是尾节点的 next 指向了之前的某个节点，形成一个闭环
- 边界条件： 空链表、只有一个节点的链表（自环或无环）、整个链表就是一个环
小白版直白理解
就像两个人在一个环形跑道上跑步，一个人跑得快（一次跑两步），一个人跑得慢（一次跑一步）。如果跑道是环形的（有环），快的人一定会追上慢的人；如果是直道（无环），快的人会先跑到终点。
具体到链表，我们用两个指针来代替人：一个一次走一步（慢指针），一个一次走两步（快指针）。如果链表里有环，它们最终会相遇；如果没环，快指针会先遇到空节点。
解题思路
思路一：快慢指针（Floyd 判圈算法，推荐）
为什么这样想： 如果链表中存在环，遍历就会无限循环。我们需要一种在不使用额外空间的情况下检测循环的方法。快慢指针的核心思想是：在环中，快指针每次比慢指针多走一步，相对速度差为 1，所以快指针一定会追上慢指针。
关键洞察： 为什么快指针要走两步而不是三步或更多？因为步数差为 1 能保证快指针不会「跳过」慢指针（在环中每轮追一步）。如果步差大于 1，在某些环长的情况下可能永远追不上。
def hasCycle(head):
"""快慢指针判环"""
if not head or not head.next:
return False
slow, fast = head, head
while fast and fast.next:
slow = slow.next # 慢指针走一步
fast = fast.next.next # 快指针走两步
if slow == fast: # 相遇则有环
return True
return False # fast 走到空，无环思路二：哈希集合法
思路讲解： 遍历链表，用集合记录访问过的节点引用。如果某个节点已经存在于集合中，说明第二次访问到它，即存在环。效率同样是 O(n)，但需要 O(n) 的额外空间。
def hasCycle(head):
"""哈希集合法"""
visited = set()
cur = head
while cur:
if cur in visited:
return True
visited.add(cur)
cur = cur.next
return False易错点
- fast.next 的空指针检查：
while fast and fast.next两者都必须检查，因为fast = fast.next.next需要 fast.next 不为空 - 空链表和单节点无环： head 为空或 head.next 为空时，不可能有环，直接返回 False
- 自环（单节点成环）： 一个节点且 next 指向自身，快慢指针会在第一轮相遇（slow = head, fast = head, 循环中 slow=slow.next=head, fast=fast.next.next=head）
- while 循环条件： 不是
while fast.next and fast.next.next，而是while fast and fast.next - 初始位置： slow 和 fast 都初始化为 head，而不是一前一后
框架提炼
快慢指针判环模板： 判断链表是否有环的通用方法。
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False这个模板是 Floyd 判圈算法的基础部分，可进一步扩展为：
- 找到环的入口（142. 环形链表 II）
- 计算环的长度
- 在数组（值域）上找重复数（287. 寻找重复数）
关联题目
- 142-环形链表II — 不仅判环，还要找到环的入口，是本题的直接进阶
- 160-相交链表 — 双指针消除长度差的思路类似
- 287-寻找重复数 — 将数组看作链表，用 Floyd 判圈法找到重复数