1. 题目概述在面试和算法分类刷题中链表环路问题是一个极其高频的考点。LeetCode142. 环形链表 II的要求给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。核心限制不允许修改链表。2. 核心解题思路快慢指针Floyd 判圈算法解决这道题最经典且空间复杂度为 O(1) 的方法就是快慢指针法也叫双指针法。我们可以把这个问题拆解为两步判断是否有环定义一个慢指针slow每次走 1 步和一个快指针fast每次走 2 步。如果它们相遇说明链表一定有环。寻找环的入口这是本题的难点。当它们相遇时我们需要通过数学关系来推导出如何找到入环点。3. 数学推导为什么相遇后能找到入口很多同学能记住“相遇后一个放开头一个在原地一起走就会在入口相遇”的结论但不知道为什么。其实它的数学推导非常漂亮。假设从头节点到环形入口的距离为 x。从环形入口到快慢指针相遇点的距离为 y。从相遇点再往前走回到环形入口的距离为 z。我们可以得出环的长度为 y z。当fast与slow相遇时slow指针走的步数S_slow x y 因为快指针是慢指针速度的两倍慢指针在入环的第一圈内必然会被追上。fast指针走的步数S_fast x y n(y z) n 为快指针在环里转的圈数n大于等于1。因为快指针的速度是慢指针的 2 倍所以存在等式2*S_slow S_fast2(x y) x y n(y z)两边同时减去一个 (x y)x y n(y z)我们要找的是入口点也就是求距离 x。我们把 x 单独留在左边x n(y z) - yx (n - 1)(y z) z结论分析当 n 1快指针多转 1 圈时x z。这意味着从头节点到环入口的距离 (x)等于从相遇点到环入口的距离 (z)。因此当快慢指针相遇时我们只需要把其中一个指针比如fast重置回头节点然后让它和仍在相遇点的slow指针一起每次只走1 步。当它们再次相遇时相遇的位置必然就是环的入口节点class Solution { public: ListNode *detectCycle(ListNode *head) { if (head nullptr || head-next nullptr) { return nullptr; } ListNode* slow head; ListNode* fast head; bool hasCycle false; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { hasCycle true; break; } } if (!hasCycle) { return nullptr; } fast head; while (fast!slow) { fast fast-next; slow slow-next; } return fast; } };
)
