文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接142.环形链表 II2、题目描述二、个人思路整理1、思路分析也可以参考博主的该博客【代码随想录】LC 142. 环形链表 II核心思路Floyd判圈算法快慢双指针法判断是否有环定义两个指针慢指针slow每次走 1 步快指针fast每次走 2 步。如果fast遇到nullptr说明链表无环直接返回nullptr。如果fast和slow相遇说明链表必定有环。寻找入环点假设头节点到入环点的距离为a aa入环点到首次相遇点的距离为b bb首次相遇点继续走到入环点的距离为c cc环的总长度为b c b cbc相遇时各指针走的距离slow走的步数S a b S a bSabfast走的步数F a n ( b c ) b F a n(b c) bFan(bc)b其中n ≥ 1 n \ge 1n≥1为快指针在环内转的圈数根据快指针速度是慢指针的 2 倍F 2 S ⟹ a n ( b c ) b 2 ( a b ) F 2S \implies a n(b c) b 2(a b)F2S⟹an(bc)b2(ab)a n ( b c ) − b ( n − 1 ) ( b c ) c a n(b c) - b (n - 1)(b c) can(bc)−b(n−1)(bc)c结论当n 1 n 1n1时a c a cac。这意味着从链表头节点出发一个指针同时从相遇点出发一个指针两者每次均走 1 步最终必定会在入环点相遇。2、解题代码/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public:ListNode*detectCycle(ListNode*head){ListNode*fasthead;ListNode*slowhead;// 1. 判断是否有环while(fast!nullptrfast-next!nullptr){fastfast-next-next;slowslow-next;// 快慢指针相遇说明有环if(fastslow){// 2. 寻找环入口ListNode*p1head;ListNode*p2slow;while(p1!p2){p1p1-next;p2p2-next;}returnp1;// 相遇点即为入环节点}}returnnullptr;// 无环}};复杂度分析时间复杂度O ( N ) O(N)O(N)。寻找相遇点和寻找入口节点各遍历最多2 N 2N2N次。空间复杂度O ( 1 ) O(1)O(1)。仅使用常数个指针变量。三、知识风暴Floyd 判圈算法快慢双指针法是本题的核心思想用一快一慢两个指针遍历链表通过「快指针能否追上慢指针」来判断是否存在环并在相遇后通过数学推导定位入环点。它把空间复杂度从哈希表的O ( n ) O(n)O(n)优化到O ( 1 ) O(1)O(1)。算法核心思想快慢指针慢指针slow每次走 1 步快指针fast每次走 2 步二者从head同时出发。判环依据若无环fast会先遇到nullptr若有环fast最终必定追上slow并相遇。相遇点定位相遇后从head和相遇点各出发一个指针每次走 1 步二者必定在入环点相遇。数学推导设头节点到入环点距离为a aa入环点到相遇点距离为b bb环长为L LL由2 ( a b ) a b n L 2(ab) a b nL2(ab)abnL可推出a n L − b a nL - banL−b即从相遇点继续走到入环点的距离与a aa相等。常见对比哈希表 vs 快慢指针方法核心思路时间复杂度空间复杂度适用场景哈希表unordered_set遍历链表将每个节点指针存入集合遇到重复即说明有环O ( n ) O(n)O(n)O ( n ) O(n)O(n)思路直观适合快速实现、不追求空间优化快慢指针Floyd 判圈快指针每次走 2 步、慢指针走 1 步相遇即有环再数学定位入环点O ( n ) O(n)O(n)O ( 1 ) O(1)O(1)空间最优是本题的标准解法使用要点判空处理head为空或只有一个节点时链表不可能有环直接返回nullptr。循环条件while (fast ! nullptr fast-next ! nullptr)保证fast-next-next不越界。相遇判断fast slow说明有环若循环正常结束说明fast走到了链表末尾无环。入环点定位相遇后令p1 head、p2 slow二者同步走 1 步首次相等处即为入环点。边界情况环可能包含整个链表入环点即head此时p1与p2在head处直接相等。算法变体与扩展只判断是否有环使用快慢指针相遇即返回true无需定位入环点对应 LeetCode 141。返回入环点在相遇后增加一步数学定位即本题 142 的做法。求环的长度相遇后让一个指针原地不动另一个指针每次走 1 步再次相遇时走过的步数即为环长。求链表长度先定位入环点再分别计算头节点到入环点、以及环的长度二者相加即为链表总长。常见对比三种指针遍历写法写法含义适用场景while (fast ! nullptr fast-next ! nullptr)快指针每次走 2 步需同时判断当前节点与下一节点非空快慢指针判环的标准写法while (p1 ! p2)两个指针同步走 1 步直到相遇定位入环点、求相遇点for (ListNode* cur head; cur ! nullptr; cur cur-next)单指针顺序遍历一般链表遍历、统计长度与其他算法的对比快慢指针Floyd 判圈O ( n ) O(n)O(n)时间、O ( 1 ) O(1)O(1)空间是本题最优解也是面试中最常考察的解法。哈希表判环O ( n ) O(n)O(n)时间、O ( n ) O(n)O(n)空间思路最简单但额外占用内存不满足进阶要求。暴力遍历对每个节点向后遍历判断是否回到自身O ( n 2 ) O(n^2)O(n2)时间仅适用于理解思路不具实用性。相关 LeetCode 例题141. 环形链表快慢指针判环本题的前置基础142. 环形链表 II本题判环 定位入环点287. 寻找重复数快慢指针思想在数组上的应用202. 快乐数快慢指针判断循环的经典应用指针声明风格ListNode* p与ListNode *p在 C以及 C 语言中ListNode* p与ListNode *p在编译器语法、生成的目标代码、运行效率和功能上没有任何区别差异仅体现在设计哲学与代码风格上ListNode* p星号靠向类型强调p的类型是ListNode*契合“类型在前”的直觉是现代 C 及 Java/C# 转 C 开发者偏好的写法。ListNode *p星号靠向变量名强调*p解引用后得到ListNode是 C 语言传统风格在 Linux 内核、STL 源码中极为常见。关键陷阱*修饰符只与其紧邻的变量名绑定。ListNode* p1, p2;中只有p1是指针p2是普通对象而ListNode *p1, *p2;则两个都是指针。建议一行只声明一个指针变量彻底避免混淆。回到本题解题代码中ListNode *detectCycle(ListNode *head)与ListNode* fast head;混用了两种风格但功能完全等价理解这一区别有助于快速抓住源码本质。
