链表专题(六)：数学与指针的完美结合——「环形链表 II」-深圳市維司達科技有限公司

场景想象：你在这个链表跑道上跑步。

第一步（判圈）：怎么知道跑道是不是圆形的（有环）？
- 很简单，派一个快跑者（Fast）和一个慢跑者（Slow）。如果快跑者能“套圈”追上慢跑者，说明肯定有环。
第二步（找入口）：如果确认有环，这个环的入口在哪里？
- 这就难了。快慢指针相遇的地方，往往不是入口，而是环里的某个随机位置。
- 我们需要用一个神奇的数学公式，把指针“变”回入口。

力扣 142. 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/

题目分析：

输入：链表头head。
目标：如果链表有环，返回链表开始入环的第一个节点。如果没有环，返回null。
输出：入口节点 Node。

核心思维：快慢指针 + 数学魔法 (`x = z`)

这道题的解法分为两个阶段：

阶段 1：相遇（判断有环）让fast每次走 2 步，slow每次走 1 步。如果fast走到null，说明没环，结束。如果fast和slow相遇了，说明有环。此时，它们停在环里的某个点（我们记为相遇点 M）。

阶段 2：寻找入口（数学推导）假设：

x：从头结点到环入口的距离。
y：从环入口到相遇点 M 的距离。
z：从相遇点 M 回到环入口的距离（剩下的环长）。

推导过程（面试加分项）：

慢指针走了：x + y
快指针走了：x + y + n(y + z)（它在环里多转了 n 圈才追上）
因为快指针速度是慢指针的 2 倍：2(x + y) = x + y + n(y + z)
消掉一个x + y：x + y = n(y + z)
我们想求入口距离x：x = n(y + z) - y
整理一下：x = (n - 1)(y + z) + z

神奇结论：当n = 1时（最简单的情况），公式简化为x = z！意思是：“头结点到入口的距离”竟然等于“相遇点到入口的距离”。

操作策略：当fast和slow相遇时：

让slow留在原地（相遇点）。
派一个新的指针（或者复用fast）回到头结点head。
两个指针同时每次走 1 步。
因为x = z，它们一定会在环的入口相遇！

代码实现 (JavaScript)

JavaScript

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var detectCycle = function(head) { let slow = head; let fast = head; // 阶段 1：快慢指针判圈 while (fast !== null && fast.next !== null) { slow = slow.next; // 慢走1步 fast = fast.next.next; // 快走2步 // 如果相遇了，说明有环 if (slow === fast) { // 阶段 2：寻找入口 // 此时 slow 在相遇点，fast 也在相遇点 // 让 fast 回到头结点（充当那个从头走的新指针） fast = head; // 两个指针每次都走 1 步，直到再次相遇 while (slow !== fast) { slow = slow.next; fast = fast.next; } // 再次相遇的点，就是环的入口 return slow; } } // 如果退出了循环，说明遇到 null 了，没环 return null; };