单链表算法题三环与数学篇前言前两篇我们学习了链表的基础操作和进阶技巧。本篇将进入链表题目中最具数学色彩的部分——环形链表。环形链表是面试中的高频考点它不仅考察代码实现能力更考察数学推理能力。很多同学能写出判断环的代码但问起为什么快慢指针一定会相遇时却答不上来。本篇将深入讲解环形链表 I— 判断链表是否有环环形链表 II— 找到环的入口节点背后的数学证明— 理解原理而不是死记代码题目一环形链表 ILeetCode 141. 环形链表给你一个链表的头节点head判断链表中是否有环。示例输入head [3,2,0,-4], pos 1尾部指向索引1 输出true 解释链表中有一个环尾部连接到第二个节点。 输入head [1,2], pos 0 输出true 输入head [1], pos -1 输出false解法快慢指针这是最经典的解法没有之一boolhasCycle(structListNode*head){if(headNULL||head-nextNULL){returnfalse;}structListNode*slowhead;structListNode*fasthead;while(fast!NULLfast-next!NULL){slowslow-next;// 慢指针走1步fastfast-next-next;// 快指针走2步if(slowfast){returntrue;// 相遇了有环}}returnfalse;// fast 到末尾了无环}代码逻辑慢指针每次走 1 步快指针每次走 2 步如果有环快指针一定会追上慢指针如果无环快指针先到达NULL数学证明一为什么慢走1步、快走2步一定会相遇这是环形链表最核心的问题。我们分步来证明第1步慢指针进环时的情况假设链表头节点到环入口的距离为L环的周长为R。L X H ───────→ E ────────→ M ↑ ↓ └─── R-X ──┘ H: 链表起点 E: 环的入口 M: 快慢指针相遇点当慢指针slow走完 L 步刚好进入环时快指针fast已经在环里走了多少了slow走 L 步 →fast走 2L 步fast在环里走的距离 2L - L L因为前 L 步到入口所以fast在环中已经走了L % R步第2步追逐过程当slow进入环时fast已经在环中某处了。设此时fast在slow前面N步沿环的顺时针方向。N 的取值范围是 1 到 R-1如果 N0说明已经在同一位置已经相遇了每次追击slow走 1 步fast走 2 步二者距离缩短2 - 1 1步所以距离的变化是N → N-1 → N-2 → ... → 1 → 0一定会追到 0✅这就是为什么慢走 1 步、快走 2 步一定会相遇。数学证明二快指针走3步、4步…可以吗快指针走 3 步的情况每次追击距离缩短3 - 1 2步。距离变化N → N-2 → N-4 → ...如果 N 是偶数最终会到 0相遇 ✅如果 N 是奇数会变成 -1即错过了距离变成R - 1进入新一轮追击距离为R - 1如果R - 1是偶数最终相遇 ✅如果R - 1是奇数永远错过 ❌看起来快指针走 3 步不一定能相遇关键问题N 是奇数且 R 是偶数这种情况存在吗我们来证明这种情况不存在假设slow走 L 步进入环fast在环中走了 L 步因为fast速度是slow的 3 倍此时fast在环中的位置 L % Rfast在slow前面 N 步满足N (L % R) 的某种表达...更严谨的推导当slow进入环时slow走了 L 步fast走了 3L 步fast在环中走了3L - L 2L步所以在环中的相对位置N (2L) % R如果 N 是奇数且 R 是偶数则(2L) % R是奇数。但2L是偶数一个偶数除以偶数的余数可能是奇数吗例子2L 10, R 610 % 6 4偶数✓2L 14, R 814 % 8 6偶数✓实际上偶数 % 偶数 偶数或 0因为设 2L kR N如果 R 和 N 都是奇数等式左边是偶数右边 奇数×奇数 奇数 偶数 奇数 奇数矛盾所以N 是奇数且 R 是偶数的情况不存在。结论快指针走 3 步最终也一定能相遇✅实践中虽然快指针走任意步数理论上都能相遇但代码实现时走 2 步最简洁也最不容易出错。所以面试中默认使用慢1步、快2步。题目九环形链表 IILeetCode 142. 环形链表 II给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。示例输入head [3,2,0,-4], pos 1 输出返回索引为 1 的节点 输入head [1,2], pos 0 输出返回索引为 0 的节点 输入head [1], pos -1 输出返回 null解法快慢指针 双指针找入口structListNode*detectCycle(structListNode*head){if(headNULL||head-nextNULL){returnNULL;}structListNode*slowhead;structListNode*fasthead;// 第1步判断是否有环找到相遇点while(fast!NULLfast-next!NULL){slowslow-next;fastfast-next-next;if(slowfast){// 有环开始找入口structListNode*meetslow;structListNode*starthead;// 第2步一个从起点走一个从相遇点走while(start!meet){startstart-next;meetmeet-next;}returnstart;// 入口节点}}returnNULL;// 无环}关键为什么一个从起点走、一个从相遇点走每次走 1 步会在入口相遇数学证明为什么两个指针会在入口相遇设L 从头节点到环入口的距离X 从入口到相遇点的距离R 环的周长n 快指针在相遇前已经绕环走了 n 圈n ≥ 1L X H ───────→ E ────────→ M ↑ ↓ └─── R-X ──┘快慢指针的路程关系当快慢指针在 M 点相遇时慢指针走的路程L X快指针走的路程L X nR多走了 n 圈因为快指针速度是慢指针的 2 倍L X nR 2(L X) L X nR 2L 2X nR L X L nR - X L (n-1)R (R - X)关键结论L (n-1)R (R - X)这个公式的含义是从起点 H到入口 E的距离 L等于从相遇点 M出发绕环走(n-1)圈再走(R - X)步到达入口 E 的距离。也就是说一个指针从 H 出发另一个从 M 出发都以 1 步的速度走它们会在 E 相遇最简情况n 1当n 1时L R - X这意味着起点到入口的距离 相遇点到入口的距离H ── L ──→ E ←── R-X ──→ M ↑ ↓ └────────────┘ 从 H 走 L 步到 E 从 M 走 (R-X) 步到 E 当 L R-X 时两者同时到达 E图解全过程链表: [1] → [2] → [3] → [4] → [5] ↑ ↓ └─── [7] ← [6] Step 1: 快慢指针追逐 slow: 1→2→3→4→5→6→7→4→5... fast: 1→3→5→7→4→6→5... 相遇在 [5] Step 2: 双指针找入口 start 从 [1] 出发: 1→2→3→4→5→6→7 meet 从 [5] 出发: 5→6→7→4→5→6→7 start 走 4 步到 [5]不对入口是 [4] 实际上: start: 1→2→3→4 (3步到入口) meet: 5→6→7→4 (3步到入口) 在 [4] 相遇✓快慢指针的三种经典应用环形链表的两道题完美展示了快慢指针的三种应用场景应用一判断是否有环while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast)returntrue;}returnfalse;应用二找到环的入口// 先找到相遇点// 再让一个从起点走一个从相遇点走// 相遇点就是入口应用三找链表中点while(fastfast-next){slowslow-next;fastfast-next-next;}// slow 就是中点常见面试追问Q1如果链表很大快慢指针会溢出吗不会。指针只存储地址不存储步数不存在溢出问题。Q2如果环很大R 很大快慢指针要追多久最坏情况下慢指针走一圈不到就能追上。因为每次距离缩小 1 步最多追 R 步时间复杂度 O®。Q3如果快指针走 4 步慢指针走 1 步还能相遇吗每次追击距离缩小 3 步需要更复杂的数学分析。虽然理论上也能相遇但代码实现会更复杂不推荐。Q4能找到环的长度吗可以在快慢指针相遇后让一个指针不动另一个继续走再次相遇时走的步数就是环的长度。intcycleLength(structListNode*head){// 先找到相遇点// 然后一个指针不动另一个走// 再次相遇时走的步数 环长}本讲总结题目核心技巧数学关键环形链表 I快慢指针每次距离缩小1步必然相遇环形链表 II快慢指针 双指针L (n-1)R (R-X)核心启示快慢指针相遇的数学原理是距离差每次缩小1环入口的证明关键是路程关系的等式推导理解数学原理比记住代码更重要思考题如果快指针每次走 3 步慢指针每次走 1 步请证明它们也一定会相遇。找到环的入口后如何计算环的长度如果一个链表既有环又很长快慢指针会不会在入环前就相遇思考在入环前快指针始终在慢指针前面不会相遇下一篇预告[单链表算法题四高级应用篇]将讲解随机链表的复制等更复杂的题目。如果你觉得这篇文章对你有帮助欢迎点赞收藏有问题请在评论区留言讨论。