知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 03 - 环形链表 & 入环点 ## 题目 - LeetCode 141:判断链表是否有环 - LeetCode 142:找到环的入口节点 ## 大白话理解 快慢指针(Floyd 判圈算法):一个走一步,一个走两步。如果有环,快指针一定会追上慢指针(就像操场跑步,跑得快的会套圈)。 ## 判断是否有环(141) ```java public boolean hasCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; // 相遇了,有环 } return false; // fast 走到头了,无环 } ``` ## 找入环点(142) ``` 相遇后,让一个指针回到头节点,两个都走一步,再次相遇的地方就是入环点。 数学证明: 设头到入环点距离 a,入环点到相遇点距离 b,环长 c 慢指针走了 a+b 步 快指针走了 a+b+nc 步(多走了 n 圈) 快指针速度是慢指针 2 倍:2(a+b) = a+b+nc → a+b = nc → a = nc-b = (n-1)c + (c-b) c-b 就是从相遇点到入环点的距离 所以从头走 a 步 = 从相遇点走 (n-1)圈 + (c-b) 步,都到达入环点 ``` ```java 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) { // 相遇了,找入环点 ListNode p = head; while (p != slow) { p = p.next; slow = slow.next; } return p; } } return null; } ``` ## 一句话总结 快慢指针判环,相遇后一个回头节点同步走找入环点。 --- 上一篇:[02 - 合并两个有序链表](./02-merge-two-lists.md) | 下一篇:[04 - 相交链表](./04-intersection.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入