链表面试天花板：环形链表（141/142）深度解析
🏠个人主页：黎雁
🎬作者简介：C/C++/JAVA后端开发学习者
❄️个人专栏：C语言、数据结构（C语言）、EasyX、JAVA、数据结构与算法（JAVA）、游戏、规划、程序人生
✨ 从来绝巘须孤往，万里同尘即玉京
文章目录
链表面试天花板：环形链表（141/142）深度解析 🌀
LeetCode 141 判断环 + 142 找环入口，快慢指针数学证明+最优模板，面试手撕不慌
📝 文章摘要
- 阅读时长：20 分钟
- 适合人群
- 链表算法进阶者 → 重点：快慢指针数学证明、环入口推导、通用结论
- 面试/笔试刷题党 → 重点：最优代码模板、边界处理、思考题解答
- 算法原理深究者 → 重点：速度差/环长/初始距离的数学关系
- 复习总结同学 → 重点：核心结论、证明过程、代码一键套用
- 本文内容
全覆盖 LeetCode 141 环形链表（判断环）+ 142 环形链表II（找环入口），包含快慢指针解法、数学证明、思考题详细解答、通用结论推导，从“会用”到“懂原理”！
🧠 前置知识回顾
做环形链表题前，你需要掌握：
- 快慢指针基础用法（步长差、相遇逻辑）
- 最大公约数（gcd）数学概念
- 链表遍历、边界判断（null 处理）
- 简单代数推导能力
这两道题是链表面试最难的经典题，掌握原理=吃透链表快慢指针所有考点！
1. 环形链表（LeetCode 141）🔍
题目：给定链表头结点 head，判断链表是否有环。若有环返回 true，否则返回 false。
思路一：快慢指针（最推荐 ✅）
核心思想
- 慢指针
slow每次走 1 步，快指针fast每次走 2 步 - 有环 →
fast会在环内追上slow（相遇） - 无环 →
fast先走到链表末尾null
完整可运行代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { this.val = val; } * } */publicclassSolution{publicbooleanhasCycle(ListNode head){// 边界：空链表/单节点链表无环if(head ==null|| head.next ==null){returnfalse;}ListNode slow = head;ListNode fast = head;// 循环条件：fast没到末尾（避免空指针）while(fast !=null&& fast.next !=null){ slow = slow.next;// 慢指针走1步 fast = fast.next.next;// 快指针走2步// 相遇则有环if(slow == fast){returntrue;}}// fast走到末尾，无环returnfalse;}}核心思考题（面试高频追问）
Q1：为什么 slow 走1步、fast 走2步一定能相遇？
数学证明：
- 当
slow进入环时，fast已经在环内，设两者初始距离为n（环内节点数差） - 每轮移动：
fast比slow多走2-1=1步，即两者距离每次缩小1 - 距离变化：
n → n-1 → n-2 → ... → 2 → 1 → 0 - 距离为 0 时必然相遇，证毕。
Q2：slow 走1步、fast 走3步，一定能追上吗？
结论：不一定，可能永远追不上 ❌
详细证明：
slow进环后，设与fast初始距离为n，环长度为C- 每轮移动：
fast比slow多走3-1=2步，距离每次缩小 2 - 分两种情况：
- n 为偶数：距离变化
n → n-2 → ... → 2 → 0→ 能相遇 - n 为奇数：距离变化
n → n-2 → ... → 3 → 1 → -1（-1 表示fast反超slow）
反超后，两者新距离为C-1：- 若
C-1为偶数 → 能相遇 - 若
C-1为奇数 → 进入死循环（距离永远是奇数，反复反超）
- 若
- n 为偶数：距离变化
Q3：slow 走2步、fast 走3步，可行吗？
结论：不一定，需满足数学条件 ✅/❌
Q4：快慢指针能追上的通用结论？
核心推导：
设：
- 慢指针步长
S，快指针步长F（F > S） - 环长度
C，slow进环时与fast初始距离n（0 ≤ n ≤ C） - 每轮速度差
d = F - S - 追上时经过
k轮，fast绕环m圈
则满足：k × d = n + m × C
变形得：k × d - m × C = n
设 g = gcd(d, C)（速度差与环长的最大公约数），则左边 k×d - m×C 必为 g 的倍数，因此：
通用结论：当且仅当「初始距离 n」是「速度差 d」和「环长 C」的最大公约数 g 的倍数时，快慢指针能相遇。
结论验证
- case1（1步+2步）：
S=1, F=2 → d=1，g = gcd(1, C) = 1
无论n是多少，都是 1 的倍数 → 必相遇 ✅ - case2（1步+3步）：
S=1, F=3 → d=2，g = gcd(2, C)C为奇数 →g=1→ 必相遇C为偶数 →g=2→ 仅当n为偶数时相遇
2. 环形链表II（LeetCode 142）🎯
题目：给定链表头节点 head，返回链表开始入环的第一个节点；无环则返回 null。
思路一：快慢指针 + 双指针找入口（最推荐 ✅）
核心思想
- 找相遇点：快慢指针（1步+2步）找到环内相遇节点
- 找入口点：头节点
head和相遇点meet各走1步，相遇处即为环入口
完整可运行代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { this.val = val; } * } */classSolution{publicListNodedetectCycle(ListNode head){// 边界：空链表/单节点链表无环if(head ==null|| head.next ==null){returnnull;}ListNode fast = head;ListNode slow = head;// 第一步：找快慢指针相遇点while(fast !=null&& fast.next !=null){ slow = slow.next; fast = fast.next.next;// 找到相遇点，开始找环入口if(slow == fast){ListNode meet = slow;// 第二步：head和meet各走1步，相遇即入口while(head != meet){ head = head.next; meet = meet.next;}return head;// 或 return meet}}// 无环returnnull;}}核心思考题证明：为什么 head 和 meet 走1步会在入口相遇？
变量定义
L：入环前链表长度（头节点 → 环入口）X：相遇点 → 环入口的距离（环内）C：环的长度N：fast 绕环的圈数（N ≥ 1）
代数推导
- fast 走的路程 = 2 × slow 走的路程
- fast 路程：
L + N×C + X（入环前 + 绕环N圈 + 相遇点到入口） - slow 路程：
L + X（入环前 + 到相遇点） - 等式：
L + N×C + X = 2 × (L + X) - 化简：
N×C = L + X→L = N×C - X - 变形：
L = (N-1)×C + (C - X)
结论解读
C - X：相遇点绕环走到入口的距离(N-1)×C：绕环N-1圈（不影响最终位置）- 因此：头节点到入口的距离
L= 相遇点绕环到入口的距离（差整数圈） - → 头节点和相遇点各走1步，必然在入口相遇 🎯
📌 核心考点总结（面试必背）
环形链表 141
- 最优解法：快慢指针（1步+2步），时间 O(n)、空间 O(1)
- 通用结论：初始距离 n 是「速度差 d」和「环长 C」最大公约数的倍数 → 能相遇
- 面试回答：优先说1步+2步解法，被追问时讲数学证明
环形链表 142
- 核心步骤：先找相遇点 → 再用双指针找入口
- 数学本质：
L = (N-1)×C + (C-X)，头节点和相遇点等速走必在入口相遇 - 代码模板：背熟！面试直接写，边界处理（空链表/单节点）不能漏
✍️ 写在最后
环形链表是链表面试的终极考点，考察的不仅是代码能力，更是数学推导和逻辑思维：
- 141 题考“是否能想到快慢指针”
- 142 题考“是否懂相遇点到入口的推导”
- 追问考“是否理解快慢指针的通用条件”
建议你：
- 背熟141/142 最优代码模板（可直接提交）
- 理解并能口述相遇证明+入口推导（面试加分）
- 记住通用结论（应对快慢指针步长追问）
至此，链表高频面试题已全部覆盖：
✅ 移除元素 ✅ 反转链表 ✅ 中间节点 ✅ 倒数第k个
✅ 合并链表 ✅ 链表分割 ✅ 回文链表 ✅ 相交链表
✅ 环形链表（判断+找入口）
掌握这些，链表面试 100% 稳过！🚀
觉得有用欢迎 👍点赞、⭐收藏、💬评论，持续更新 Java 数据结构与 LeetCode 算法精讲～
