知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 27 - 环形链表II ## 题目(LeetCode 142) 找到环形链表的入环节点。 ## 解法:快慢指针 ```java class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } } return null; } } ``` > 💬 **Q:找入环节点部分的逻辑是什么?为什么不能在快慢指针相遇时直接 return slow?** > > 因为相遇点不是入环点,而是环内的某个中间位置。数学推导如下: > > ``` > head → ... → 入环点 → ... → 相遇点 → ... → 入环点 > |← a →|← b →| |← c →| > ``` > > - slow 走了 `a + b` 步,fast 走了 `a + b + n(b+c)` 步(多绕 n 圈) > - fast 速度是 slow 的 2 倍:`2(a+b) = a + b + n(b+c)` > - 化简:**`a = (n-1)(b+c) + c`** > > 这个等式说明:从 head 走 `a` 步到入环点的距离,恰好等于从相遇点走 `c` 步(再绕若干整圈)到入环点的距离。 > > 所以代码的做法是: > 1. 快慢指针相遇后,把 slow 重置回 head > 2. slow 和 fast 都改为每次走 1 步 > 3. 它们再次相遇的位置就是入环点 > > 举个具体例子:`1 → 2 → 3 → 4 → 5 → 3`(节点 3 入环) > - a=2, b=0 时相遇在节点 3,恰好就是入环点(特殊情况) > - 但如果 `1 → 2 → 3 → 4 → 5 → 3`,a=2, 环长=3,相遇可能在节点 5(不是入环点),此时必须走第二阶段才能找到节点 3 ## 复杂度 - 时间 O(n),空间 O(1) ## 一句话总结 快慢指针相遇后,一个回到头部,两个同速走,再次相遇就是入环点。 ## 说明 找环入口的快慢指针解法是最优解(O(n) 时间,O(1) 空间),数学推导保证了相遇后一个指针回到头部同速走必然在入口相遇。 HashSet 记录已访问节点也可以找到入口,但空间 O(n)。当前解法已是最优。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入