第4章｜链表

Unit 08 · 环形链表 II：从相遇点定位环入口

← Unit 07
仅本次页面有效
U08
Linked List Cycle IIMeet · Reset · Walk · Entry

第一次相遇只证明有环，
第二次相遇才定位入口。

Unit 07 已经解决“是否存在环”。本单元继续追问：不使用额外集合，怎样从快慢指针的第一次相遇点，精确返回环开始的节点？关键不是记住“再放一个指针”，而是理解两段距离为什么相等。

发现上次学习记录可恢复阶段、动画、代码、脚手架和滚动位置。
LeetCode #142 题目模型返回环入口节点；无环返回 None；不能修改链表

题目要求

给定链表头节点 head，若链表中存在环，返回环开始的节点；若不存在环，返回 None。评测中的 pos 只用于描述尾节点连接到哪个位置，不会作为函数参数传入。

class Solution: def detectCycle( self, head: Optional[ListNode] ) -> Optional[ListNode]: pass

复杂度目标

  • 时间复杂度：O(n)；
  • 额外空间复杂度：O(1)；
  • 比较节点身份，而不是节点值。

示例

head = [3,2,0,-4], pos = 1
输出：返回值为 2 的节点对象
解释：尾节点连接到索引 1 的节点。
head = [1,2], pos = 0
输出：返回值为 1 的头节点。
head = [1], pos = -1
输出：None

本页主模型

第一阶段用 Floyd 快慢指针找到环内相遇点；第二阶段令 finder = head，再让 finder 与 slow 每轮各走一步，最终在环入口相遇。

与 Unit 07 的直接联系

Unit 07：hasCycle

第一次出现 slow is fast 就能返回 True。答案只需要布尔值。

→
Unit 08：detectCycle

第一次相遇不能直接返回。需要恢复一个从 head 出发的指针，再进行第二次同步移动。

Cycle Entry 环入口

从 head 沿 next 第一次进入循环区域的节点。它不一定等于快慢指针第一次相遇点。

Meeting Point 相遇点

第一阶段中 slow 与 fast 引用同一节点的位置。它只证明存在环，并提供第二阶段的起点。

Tail Length a

从 head 到环入口需要走的边数。无环前缀也常称为链表的“尾部”或非环部分。

Cycle Length λ

环中节点数量。若相遇点距离入口还需 c 步，则 head 到入口的距离与 c 在模 λ 意义下相等。

认知任务 1
题目要返回“环入口”，不是第一次相遇点
观察当前链表：从 head 出发第一次进入重复循环的位置是哪一个节点？
链表、环与指针动画点击节点或使用步骤控制回答问题
① 检测并相遇
② finder 回到 head
③ 同步走到入口
当前阶段理解输出
slow / meeting—
fast / finder—
已访问节点0
距离关系a = 1
当前结论尚未返回
扫描
第一次相遇
finder=head
同步一步
返回入口
入口节点是从 head 首次进入循环的节点；第一次相遇点可能位于环内其他位置。
当前阶段可随时返回，进度不会清空。
关键代码补全初始化可获骨架；两阶段逻辑需独立完成
from typing import Optional class Solution: def detectCycle(self, head): slow = fast = while : slow = fast = if : finder = while : finder = finder.next slow = slow.next return return None
分层提示
进入函数。
阶段初始化
slow—
fast—
finder—
身份判断False
返回状态未返回
完成代码联动后进入 LeetCode #287 官方原题迁移代码正确或完整播放执行轨迹后解锁；查看提示与填入初始化骨架不会解锁。

迁移题：LeetCode #287《寻找重复数》

把数组解释为一条隐式链表：下标是状态，nums[index] 是唯一后继。迁移目标不是背诵另一段 Floyd 代码，而是证明为什么“重复数字”恰好对应隐式环入口。

LeetCode #287｜寻找重复数

打开 LeetCode 官方原题 ↗
中等数组双指针Floyd
题目要求

给定包含 n+1 个整数的数组 nums，每个整数都在 [1,n] 中。数组中只有一个整数重复出现，但它可能出现两次或多次。返回这个重复整数。

class Solution: def findDuplicate(self, nums: List[int]) -> int: pass
官方示例与约束
  • [1,3,4,2,2] → 2
  • [3,1,3,4,2] → 3
  • [3,3,3,3,3] → 3
  • nums.length = n+1，1 ≤ n ≤ 10⁵
  • 不能修改数组，只使用 O(1) 额外空间。
读题检查 1｜以下哪种做法违反题目约束？
题目不仅要求返回重复数，还限制不能修改数组且只用常量额外空间。
读题检查 2｜“只有一个重复整数”意味着什么？
观察官方示例 [3,3,3,3,3]。
#142：显式链表

节点对象是状态；node.next 给出唯一后继；环入口是从 head 首次进入循环的位置。

→
#287：隐式链表

数组下标是状态；nums[index] 给出唯一后继；重复数字是两个或更多下标共同指向的入口。

结构角色#142#287
起点head下标 0
一步转移node.nextnums[index]
第一次相遇环内 meeting隐式环内 meeting
第二阶段重置finder = headfinder = 0
入口含义环入口节点重复整数
排列 Floyd 的四个语义阶段

先点击阶段，构造完整处理顺序。

正确顺序应体现：先进入隐式链，再相遇，最后定位入口。

只填写四个语义槽位

每个槽位代表一个算法责任，而不是机械拆成八个零散空格。

四项全部正确后，页面才会展示组装后的结构代码。
slow = nums[0]
fast = nums[nums[0]]

while slow != fast:
    slow = nums[slow]
    fast = nums[nums[fast]]

finder = 0
while finder != slow:
    finder = nums[finder]
    slow = nums[slow]

return finder

官方样例轨迹｜nums = [1,3,4,2,2]

隐式状态链：0 → 1 → 3 → 2 → 4 → 2 → …状态 1 / 1
阶段映射
slow—
fast—
finder / 返回—
先把数组解释为确定性后继关系。

独立重写｜不再提供占位符或完整答案

完成样例轨迹后，用自己的变量名重写可提交代码。检查器只验证关键结构。

必须先把官方样例运行到返回 2，再提交独立重写。
完成后停留在本页

可继续复看距离推导、无环轨迹与 #287 官方样例，不会自动跳转。

手动进入 Unit 09 →
Unit 08 已完成。页面不会自动跳转；刷新后仍会恢复当前学习位置。
触发信号不仅判断有环，还要返回循环开始位置
第一阶段slow 走 1 步，fast 走 2 步，找到相遇点
第二阶段finder=head，与 slow 每轮各走 1 步
核心关系head→entry 与 meeting→entry 的剩余距离同余
正确比较finder is slow，比较节点身份
迁移方向数组隐式链表、重复数、确定性状态环入口