第4章｜链表
Unit 07 · 快慢指针判断链表是否有环
环不是“值重复”，
而是沿 next 再次回到同一个节点。
本单元把 Unit 06 的快慢指针从“定位中点”迁移为“识别循环”。真正需要观察的不是节点值，而是两个指针是否引用同一个节点对象。
检测到上次学习记录可以恢复阶段、动画、代码、脚手架和滚动位置。
LeetCode #141 题目模型判断是否存在沿 next 可重复到达的节点
题目要求
给定单链表头节点 head，判断链表中是否存在环。若某个节点能够通过不断沿 next 再次到达自身，则链表有环。
class Solution:
def hasCycle(
self,
head: Optional[ListNode]
) -> bool:
pass
重要说明
pos只用于描述尾节点连接到哪个位置，不作为函数参数；- 节点值可以重复，不能依赖
val判断是否相遇； - 目标是返回布尔值，不需要定位环入口。
示例
head = [3,2,0,-4], pos = 1
输出：True
尾节点 -4 的 next 指向索引 1 的节点 2。
输出：True
尾节点 -4 的 next 指向索引 1 的节点 2。
head = [1,2], pos = 0
输出：True
输出：True
head = [1], pos = -1
输出：False
输出：False
数据范围
节点数量不超过 10⁴；节点值可能重复；空链表和单节点无环链表都必须安全处理。
与 Unit 06 的联系
Unit 06：中间结点
速度比 2:1，把链表长度的一半编码到 slow 的位置。
→
Unit 07：环形链表
速度比仍是 2:1，但关注环内相对距离是否最终归零。
Cycle 环
沿 next 连续前进时，会再次访问某个已经访问过的节点对象。
Identity 身份
两个变量引用同一节点对象。值相等不代表身份相同。
Relative Speed 相对速度
fast 每轮比 slow 多走一步；进入环后，两者环上距离每轮变化 1。
Safe Exit 安全退出
若无环，fast 或 fast.next 会先到 None；双重判空避免访问 None.next。
认知任务 1
先判断：什么情况才叫“链表有环”？
不要先看快慢指针。先区分节点值重复与节点身份重复。
链表状态动画节点位置只是布局，真正结构由 next 决定
尾节点重新指向 n2
slown1
fastn1
比较身份未比较
循环条件未检查
当前结论未判断
已访问身份 / 环上相对距离
错误依据slow.val == fast.val ?
正确依据slow is fast ?
初始化 slow 与 fast，它们都指向 head。
检查边界
slow 走 1
fast 走 2
比较身份
返回结果
阶段 1 / 6可随时返回，仅本次页面有效；完成后不会自动跳题
关键表达式补全只填写 7 个关键位置
from typing import Optional
class Solution:
def hasCycle(self, head):
slow =
fast =
while :
slow =
fast =
if :
return True
return
只有代码补全正确或播放完整轨迹才会解锁迁移。提示与初始化骨架不会直接解锁。
分层提示
进入函数。
slow—
fast—
slow.val—
fast.val—
身份相同False
返回状态未返回
完成代码联动后进入官方迁移题：LeetCode #202 快乐数仅代码正确或播放完整轨迹后解锁；查看提示与填入骨架不会解锁。
迁移题：LeetCode #202《快乐数》
把显式链表中的 node.next 抽象成确定性状态转移 next_value(x)。迁移的核心不是复制代码，而是判断：状态是否会到达成功出口 1，还是进入一个不含 1 的循环。
202. Happy Number · Easy
给定正整数 n，不断把它替换为各位数字平方和。若过程最终到达 1，则返回 True；若进入一个不包含 1 的循环，则返回 False。
class Solution:
def isHappy(self, n: int) -> bool:
pass
输入：n = 19
输出：true
过程：19 → 82 → 68 → 100 → 1
输入：n = 2
输出：false
约束与输出契约
1 ≤ n ≤ 2³¹ - 1；- 每一步由“各位数字平方和”唯一确定；
- 返回布尔值，不需要输出状态序列；
- 到达 1 是成功出口；重复非 1 状态说明进入失败环。
题面、示例与约束来自 LeetCode 官方页面。打开官方原题 ↗
读题检查 1｜19 为什么是快乐数？
先识别题目的成功出口。
读题检查 2｜若重复出现非 1 状态，意味着什么？
确定性转移中，相同状态会产生相同后继。
#141 与 #202：同一种“确定性状态链”，不同的状态身份
| 维度 | #141 环形链表 | #202 快乐数 |
|---|---|---|
| 状态 | 节点对象身份 | 当前整数值 |
| 一步转移 | node = node.next | x = next_value(x) |
| 重复判据 | slow is fast | slow == fast |
| 成功出口 | 无；只判断是否有环 | fast == 1 |
| 无环/失败出口 | fast 到达 None → False | 在到达 1 前相遇 → False |
为什么 #202 可以比较整数值，而 #141 必须比较节点身份？
关注“什么信息足以唯一决定下一状态”。
把 Floyd 环检测映射到数字状态链
槽位 1｜生成下一状态
从整数中逐位取数并累加平方。
槽位 2｜制造初始速度差
避免 slow 与 fast 在移动前因同为 n 而立即相等。
槽位 3｜继续条件
尚未到达成功出口，并且快慢状态尚未相遇。
槽位 4｜速度更新
slow 一次转移，fast 两次转移。
四个槽位共同定义“状态、出口、相对速度和相遇”。
官方样例轨迹｜n = 19
初始化 slow=19，fast=82，先制造速度差。
1 / 4
slow19
fast82
循环条件True
当前结论继续
独立重写｜不要再填占位符
基于刚才的语义映射，独立写出 Floyd 版本。检查器只验证关键结构，不会自动填入答案。
先把官方样例运行到 1，再检查独立重写。
迁移分层提示
完成后停留在本页
手动进入 Unit 08 →可以继续复看显式环与隐式环的差异，或手动进入 Unit 08。
Unit 07 已完成：你已经从显式链表环迁移到隐式状态环。页面不会自动跳转。
触发信号沿确定的 next 关系可能永远无法到达终点
核心表示slow 走 1 步，fast 走 2 步
循环不变量进入环后 fast 每轮相对 slow 多走 1 步
正确比较slow is fast，比较节点身份
安全边界while fast and fast.next
迁移方向隐式状态环、快乐数、重复状态检测