解密链表环的起点：LeetCode 142 题
解密链表环的起点：LeetCode 142 题
视频地址
因为想更好的为大佬服务，制作了同步视频，这是Bilibili的视频地址
🌟 引言
链表环检测问题在C++中同样是一个经典面试题。本文将用C++实现LeetCode 142题"环形链表II"的解决方案，深入讲解快慢指针算法的原理和实现细节。
🔍 问题描述
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 nullptr。
🧠 解题思路回顾
快慢指针算法
- 使用两个指针：
slow每次走一步，fast每次走两步 - 如果两指针相遇，说明链表有环
- 将其中一个指针重置到链表头，然后两指针以相同速度前进
- 再次相遇的位置就是环的起点
数学原理
设：
- 链表头到环起点距离：
a - 环起点到相遇点距离：
b - 相遇点到环起点距离：
c
则有：
- 第一次相遇时：
slow走了a+b，fast走了a+b+c+b - 因为
fast速度是slow的两倍：2(a+b) = a+2b+c - 推导得：
a = c
💻 C++代码实现
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public: ListNode *detectCycle(ListNode *head){// 边界条件处理if(head ==nullptr|| head->next ==nullptr){returnnullptr;} ListNode *slow = head; ListNode *fast = head;// 第一阶段：检测是否有环while(fast !=nullptr&& fast->next !=nullptr){ slow = slow->next; fast = fast->next->next;if(slow == fast){break;// 相遇说明有环}}// 检查是否因为无环退出循环if(fast ==nullptr|| fast->next ==nullptr){returnnullptr;}// 第二阶段：寻找环起点 slow = head;// 重置慢指针到头部while(slow != fast){ slow = slow->next; fast = fast->next;}return slow;// 相遇点即为环起点}};🛠 代码解析
数据结构定义
structListNode{int val; ListNode *next;ListNode(int x):val(x),next(NULL){}};这是LeetCode标准的链表节点定义，包含一个整数值和指向下一个节点的指针。
算法实现细节
寻找环起点：
slow = head;// 重置慢指针到头部while(slow != fast){ slow = slow->next; fast = fast->next;}根据数学推导，两指针以相同速度前进，再次相遇点即为环起点。
无环检查：
if(fast ==nullptr|| fast->next ==nullptr){returnnullptr;}如果因为快指针无法前进而退出循环，说明无环。
环检测阶段：
while(fast !=nullptr&& fast->next !=nullptr){ slow = slow->next; fast = fast->next->next;if(slow == fast){break;// 相遇说明有环}}快指针每次走两步，慢指针每次走一步，直到相遇或快指针无法前进。
指针初始化：
ListNode *slow = head; ListNode *fast = head;快慢指针都从头节点开始。
边界条件处理：
if(head ==nullptr|| head->next ==nullptr){returnnullptr;}处理空链表或单节点链表的特殊情况。
🚀 性能分析
- 时间复杂度：O(n)
- 最坏情况下需要遍历链表两次
- 空间复杂度：O(1)
- 只使用了固定数量的指针变量
🐞 常见问题与调试
常见错误
- 初始条件处理：
忘记处理空链表或单节点链表的情况。 - 指针重置错误：
在第二阶段错误地重置了快指针而不是慢指针。
空指针访问：
while(fast !=nullptr&& fast->next !=nullptr)必须同时检查fast和fast->next，否则可能访问空指针的next成员。
调试技巧
- 小规模测试：
- 无环链表：1->2->3->null
- 有环链表：1->2->3->4->2（环在节点2）
- 边界测试：
- 空链表
- 单节点自环链表
- 双节点互相指向的链表
打印指针地址：
cout <<"Slow: "<< slow <<" Fast: "<< fast << endl;帮助跟踪指针移动情况。
📊 复杂度对比表
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 哈希表法 | O(n) | O(n) | 需要简单实现时 |
| 快慢指针 | O(n) | O(1) | 需要节省空间时 |
🌈 总结
通过C++实现的快慢指针算法，我们能够高效地解决链表环检测问题。关键在于：
- 理解快慢指针相遇的数学原理
- 正确处理边界条件和指针访问
分两个阶段实现：环检测和环起点定位
这种方法不仅高效（O(n)时间，O(1)空间），而且体现了算法设计的巧妙之处。掌握这个技巧，你就能轻松应对链表相关的各种环检测问题了！