在链表相关的算法题中「判断链表是否有环」以及「寻找入环点」是两道极其经典的题目。它们不仅考察了对指针的操作更蕴含了一个巧妙的数学原理——Floyd判圈算法龟兔赛跑算法。一、 LeetCode 141判断链表中是否有环题目链接题目要求给定一个链表判断链表中是否有环。1. 核心思想快慢指针龟兔赛跑如果在直线跑道上跑得快的人一定会先到达终点但如果是在环形跑道上跑得快的人最终一定会从背后追上套圈跑得慢的人。我们设定两个指针慢指针slow每次移动 1 步。快指针fast每次移动 2 步。2. 逻辑推演无环情况fast 指针会率先走到链表末尾nullptr此时循环结束返回 false。有环情况fast 指针进入环后会在环内不断循环。由于 fast 每次比 slow 多走 1 步两者的距离会不断缩小最终必定在环内某处相遇slow fast此时返回 true。3. 代码实现 (C)class Solution { public: bool hasCycle(ListNode *head) { if (head nullptr || head-next nullptr) return false; ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; // 慢指针走一步 fast fast-next-next; // 快指针走两步 if (slow fast) return true; // 相遇即有环 } return false; } };复杂度分析时间复杂度 O(N)空间复杂度 O(1)。二、 LeetCode 142寻找入环的第一个节点题目链接题目要求如果链表有环返回入环的第一个节点无环则返回 null。这道题在 141 的基础上增加了难度不仅要知道有没有环还要精准定位环的入口。这需要用到一段精妙的数学推导。1. 变量定义假设从头节点到入环点的距离为 a从入环点到快慢指针相遇点的距离为 b从相遇点再回到入环点的距离为 c。环的总长度为 b c。2. 数学证明为什么相遇后从头走和从相遇点走会碰头当快慢指针相遇时慢指针slow走过的路程a b快指针fast走过的路程a b n * (b c) n 为快指针在环内转的圈数n 1因为快指针的速度是慢指针的两倍所以相同时间内快指针走过的路程是慢指针的 2 倍2 * (a b) a b n * (b c)化简等式a b n * (b c) a n * (b c) - b a (n - 1) * (b c) c结论解读(n - 1) * (b c) 代表在环内转了 (n-1) 个整圈。这说明从头节点走到入环点的距离a等于从相遇点走到入环点的距离c加上转了若干整圈。3. 算法设计基于上述数学结论我们可以在快慢指针相遇后开启第二阶段让一个指针 ptr 重新回到头节点 head。让 ptr 和相遇点的 slow 指针同时出发每次各走 1 步。由于 a 的长度等同于 c加上整数圈这两个指针必定会在入环点相遇。4. 代码实现 (C)class Solution { public: ListNode *detectCycle(ListNode *head) { if (head nullptr || head-next nullptr) return nullptr; ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { // 1. 找到相遇点 ListNode *ptr head; // 2. 指针回到头节点 // 3. 两指针同速前进相遇点即为入环点 while (ptr ! slow) { ptr ptr-next; slow slow-next; } return ptr; } } return nullptr; // 无环 } };复杂度分析时间复杂度 O(N)空间复杂度 O(1)。
在链表相关的算法题中「判断链表是否有环」以及「寻找入环点」是两道极其经典的题目。它们不仅考察了对指针的操作更蕴含了一个巧妙的数学原理——Floyd判圈算法龟兔赛跑算法。一、 LeetCode 141判断链表中是否有环题目链接题目要求给定一个链表判断链表中是否有环。1. 核心思想快慢指针龟兔赛跑如果在直线跑道上跑得快的人一定会先到达终点但如果是在环形跑道上跑得快的人最终一定会从背后追上套圈跑得慢的人。我们设定两个指针慢指针slow每次移动 1 步。快指针fast每次移动 2 步。2. 逻辑推演无环情况fast 指针会率先走到链表末尾nullptr此时循环结束返回 false。有环情况fast 指针进入环后会在环内不断循环。由于 fast 每次比 slow 多走 1 步两者的距离会不断缩小最终必定在环内某处相遇slow fast此时返回 true。3. 代码实现 (C)class Solution { public: bool hasCycle(ListNode *head) { if (head nullptr || head-next nullptr) return false; ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; // 慢指针走一步 fast fast-next-next; // 快指针走两步 if (slow fast) return true; // 相遇即有环 } return false; } };复杂度分析时间复杂度 O(N)空间复杂度 O(1)。二、 LeetCode 142寻找入环的第一个节点题目链接题目要求如果链表有环返回入环的第一个节点无环则返回 null。这道题在 141 的基础上增加了难度不仅要知道有没有环还要精准定位环的入口。这需要用到一段精妙的数学推导。1. 变量定义假设从头节点到入环点的距离为 a从入环点到快慢指针相遇点的距离为 b从相遇点再回到入环点的距离为 c。环的总长度为 b c。2. 数学证明为什么相遇后从头走和从相遇点走会碰头当快慢指针相遇时慢指针slow走过的路程a b快指针fast走过的路程a b n * (b c) n 为快指针在环内转的圈数n 1因为快指针的速度是慢指针的两倍所以相同时间内快指针走过的路程是慢指针的 2 倍2 * (a b) a b n * (b c)化简等式a b n * (b c) a n * (b c) - b a (n - 1) * (b c) c结论解读(n - 1) * (b c) 代表在环内转了 (n-1) 个整圈。这说明从头节点走到入环点的距离a等于从相遇点走到入环点的距离c加上转了若干整圈。3. 算法设计基于上述数学结论我们可以在快慢指针相遇后开启第二阶段让一个指针 ptr 重新回到头节点 head。让 ptr 和相遇点的 slow 指针同时出发每次各走 1 步。由于 a 的长度等同于 c加上整数圈这两个指针必定会在入环点相遇。4. 代码实现 (C)class Solution { public: ListNode *detectCycle(ListNode *head) { if (head nullptr || head-next nullptr) return nullptr; ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { // 1. 找到相遇点 ListNode *ptr head; // 2. 指针回到头节点 // 3. 两指针同速前进相遇点即为入环点 while (ptr ! slow) { ptr ptr-next; slow slow-next; } return ptr; } } return nullptr; // 无环 } };复杂度分析时间复杂度 O(N)空间复杂度 O(1)。
