使用快慢指针可判断链表是否有环并找到入口点。首先，slow和fast指针从头节点出发，slow每次走一步，fast走两步；若fast与slow相遇，则存在环。接着，将slow重置为头节点，两指针同步前进，再次相遇处即为环入口。原理在于：设头到入口距离为a，相遇点距入口为b，环剩余为c，由2(a+b)=a+2b+c得a=c，故从头和相遇点同时出发会于入口相遇。C++实现中，先通过循环判断是否相遇，无环则返回nullptr；有环则重定位slow至头节点，两指针同速前行直至相遇，返回该节点。此法时间复杂度O(n)，空间复杂度O(1)，适用于面试高频考点。
在C++中判断链表是否有环，并找到环的入口点，通常使用快慢指针（Floyd判圈法）。这种方法高效且不需要额外存储空间，时间复杂度为O(n)，空间复杂度为O(1)。
1. 判断链表是否存在环
使用两个指针，一个慢指针每次前进一步，一个快指针每次前进两步。如果链表存在环，快指针最终会追上慢指针。
步骤：
- 初始化两个指针：slow 和 fast，都指向头节点。
- 循环移动：slow = slow->next，fast = fast->next->next。
- 如果 fast == slow，说明有环；如果 fast 或 fast->next 为 nullptr，则无环。
2. 找到环的入口节点
当快慢指针相遇后，将其中一个指针重新指向头节点，然后两个指针都以每次一步的速度前进。它们再次相遇的位置就是环的入口。
立即学习“C++免费学习笔记（深入）”；
原理简述：
- 设从头到环入口距离为 a，环入口到相遇点为 b，环剩余部分为 c。
- 慢指针走了 a + b 步，快指针走了 a + b + c + b = a + 2b + c。
- 因为快指针速度是慢指针的两倍：2(a + b) = a + 2b + c → a = c。
- 所以从头节点和相遇点同时出发，一步一走，会在入口相遇。
3. C++ 实现代码
以下是一个完整的示例实现：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
<p>ListNode<em> detectCycle(ListNode</em> head) {
if (!head || !head->next) return nullptr;</p><pre class='brush:php;toolbar:false;'>ListNode* slow = head;
ListNode* fast = head;
// 第一步：找相遇点
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
// 如果没有相遇，说明无环
if (!fast || !fast->next) return nullptr;
// 第二步：找环入口
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // 返回环入口节点}
基本上就这些。只要理解快慢指针的运行规律和数学推导，就能轻松定位环的入口。这个方法在面试中非常常见，建议熟练掌握。
