142. 环形链表 II
3 min
题目
解法：双指针
思路
使用Floyd判圈算法（快慢指针）。快指针每次走两步，慢指针每次走一步，若相遇则证明有环。相遇后重置一个指针到头部，两指针同速移动，再次相遇点即为环入口。
正确性基于距离关系：设头到入口距离a，入口到相遇点距离b，相遇点到入口剩余距离c。由2(a+b)=a+b+k(b+c)推导出a=c+(k-1)(b+c)，表明头节点和相遇点同步移动必然在入口相遇。
- Step 1: 初始化快慢指针指向头节点
- Step 2: 快指针每次走两步，慢指针每次走一步，直到相遇或快指针到null
- Step 3: 相遇后，将一个指针重置到head
- Step 4: 两指针同速移动，再次相遇点即为环入口
复杂度
- 时间复杂度: ，快慢指针遍历链表的时间，n为链表长度
- 空间复杂度: ，仅使用两个指针的常数空间
代码
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
// 相遇说明有环
if (fast == slow) {
ListNode* index1 = fast; // 相遇点
ListNode* index2 = head; // 起点
// 两个指针每次走一步，相遇点即为环入口
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
// 相遇说明有环
if (fast == slow) {
ListNode* index1 = fast; // 相遇点
ListNode* index2 = head; // 起点
// 两个指针每次走一步，相遇点即为环入口
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;
}
};