本题采用双阶段双指针算法Floyd 判圈算法的外延拓展解决单链表环路入口节点的精准定位问题。其核心本质是利用快慢指针在同向拓扑结构中的速度差锁定碰撞点再通过代数几何位移等价性引入第三指针进行二次同步步进。当前提供的源码实现了在时间复杂度 O(N) 和额外空间复杂度 O(1) 条件下的全局最优线性检索最终走向是精准定位并返回环路入口的首个节点内存地址。一、 问题本质与数据模型对于由ListNode构成的单链表若其内部存在环路其物理拓扑结构可抽象为两部分非环线性段与闭合环路段。为了定量分析其空间几何关系定义以下物理度量X从链表头节点head到环路入口节点的位移步数。Y从环路入口节点到快慢指针首次相遇碰撞节点的位移步数。Z从碰撞节点继续向前移动到环路入口节点的剩余位移步数。环路总长度恒等于 Y Z。单向常规检索无法在不破坏链表拓扑结构的前提下直接识别入口而哈希表记录法则会产生额外的线性空间损耗。本算法通过两阶段指针状态演进利用固定的代数位移等价关系锁定目标节点。二、 算法演进对比在解决环路入口检测问题时双阶段指针法在时空资源的综合利用率上达到了极限解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷哈希表物理记录法O(N)O(N)遍历链表并存储已访问节点的内存地址首个发生冲突的重复节点即为入口空间消耗随链表长度线性膨胀无法满足 O(1) 的常数阶内存约束双阶段双指针法当前解法O(N)O(1)第一阶段通过快慢步长差锁定环内碰撞点第二阶段利用代数等价性同步推进锁定入口相比基础判圈算法状态机控制分支增加内部逻辑需要精确的代数证明支撑三、 核心分支控制逻辑与决策证明当前源码的控制流分为两个串联阶段其内部决策分支及数学逻辑证明如下阶段一环路判定与碰撞点锁定控制流运行于外层while (fast ! null fast.next ! null)边界内。慢指针slow单次迭代步进 1 个节点slow slow.next。快指针fast单次迭代步进 2 个节点fast fast.next.next。数学证明当快慢指针在环内首次相遇fast slow时设慢指针总共移动了s步则快指针总共移动了2s步。假设此时快指针已经在环内循环绕行了n圈n 1根据两者的物理位移可得slow 移动距离s X Yfast 移动距离2s X Y n * (Y Z)将两式联立化简2 * (X Y) X Y n * (Y Z)X Y n * (Y Z)X n * (Y Z) - YX (n - 1) * (Y Z) Z阶段二入口同步检索当触发if (fast slow)条件时第一阶段结束程序立刻启动内层while (head ! slow)指针重组控制流。决策证明根据化简结果X (n - 1) * (Y Z) Z该公式表明从链表头节点到环路入口的距离X在数值上恒等于“n - 1圈环路长度”加上“从碰撞点到环路入口的剩余距离Z”。因此此时将指针head放置在链表起点慢指针slow保持在碰撞点两者同时以每次 1 步的恒定速度向前步进head head.next; slow slow.next;。当head指针移动X步到达环路入口时slow指针也刚好在环内移动了(n - 1)圈并走完Z步同样精准抵达环路入口。结论两指针再次重合head slow的位置必然是环路的第一个入口节点。四、 算法执行状态机步进示例以输入链表head [3, 2, 0, -4]环路连接位置pos 1即-4的next指向2此时X 1, Y 2, Z 1为例状态机的演进过程如下步骤慢指针 (slow)快指针 (fast)头指针 (head)状态判定条件执行的核心剪枝与决策动作空间物理剩余状态说明初始3 (值)3 (值)3 (值)fast ! null触发阶段一快慢指针启动步进指针均在起点尚未进入环路检测12 (值)0 (值)3 (值)2 ! 0持续步进slow走 1 步fast走 2 步slow进入入口fast深入环内20 (值)2 (值)3 (值)0 ! 2持续步进slow走 1 步fast绕环步进fast跨过衔接点追赶slow3-4 (值)-4 (值)3 (值)fast slow满足碰撞条件锁定碰撞节点-4启动阶段二第一阶段收敛slow留在原处准备与head对齐42 (值)-4 (值)2 (值)head slowhead与slow各向前步进 1 步触发终止满足相等条件精准捕获入口节点2触发返回五、 源码实现Java/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val x; * next null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { // 初始化快慢指针分别指向链表头节点 ListNode fast head; ListNode slow head; // 阶段一边界安全控制防止链表无环时发生空指针越界 while (fast ! null fast.next ! null) { // 快指针单次步进 2 个节点 fast fast.next.next; // 慢指针单次步进 1 个节点 slow slow.next; // 成功在环内相遇锁定碰撞状态 if (fast slow) { // 阶段二利用代数等价位移关系引入 head 指针同步寻找入口 while (head ! slow) { head head.next; slow slow.next; } // 指针重合点即为环路的第一个入口节点 return head; } } // 若 while 循环因触底 null 退出证明链表无环返回 null return null; } }六、 复杂度分析1. 时间复杂度O(N)分析第一阶段找碰撞点慢指针移动到入口需要X步进入环后快指针最多在Y Z即一圈长度步内追上慢指针。因为X Y Z N链表总节点数所以该阶段耗时在线性阶 O(N) 以内。第二阶段找入口点head指针和slow指针同步向前移动精确移动X步后相遇。结论两阶段的步进总次数与链表中的总节点数N呈严格的线性正比关系。2. 空间复杂度O(1)分析算法在执行全流程中仅在栈内存中分配并复用了fast、slow以及输入参数head三个基础引用变量进行位置标记与状态转移。结论完全没有申请任何与输入链表规模呈依赖关系的外部存储结构内存消耗保持为常数阶。