🌟 引言
链表环检测问题在 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) {}
* };
*/
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) {
break; // 相遇说明有环
}
}
// 检查是否因为无环退出循环
if (fast == nullptr || fast->next == nullptr) {
return nullptr;
}
// 第二阶段：寻找环起点
slow = head; // 重置慢指针到头部
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // 相遇点即为环起点
}
};
🛠 代码解析
数据结构定义
struct ListNode {
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) {
return nullptr;
}
如果因为快指针无法前进而退出循环，说明无环。
环检测阶段：
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) {
return nullptr;
}
处理空链表或单节点链表的特殊情况。
🚀 性能分析
- 时间复杂度：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) 空间），而且体现了算法设计的巧妙之处。掌握这个技巧，你就能轻松应对链表相关的各种环检测问题了！
