【牛客题霸每日一题】NC3 链表中环的入口节点 题解
在快慢指针判断有环的基础上，有：
设 紫色 点为快慢指针相遇的点，此时快指针走了 a + b + c + b，慢指针走了 a + b（若走了 k 圈类似可证），快指针是慢指针两倍速度，所以有 a + b + c + b = 2(a + b)，故 a = 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) {
ListNode *slow = head, *fast = head;
while (fast != nullptr) {
slow = slow->next;
if (fast->next == nullptr) {
return nullptr;
}
fast = fast->next->next;
if (fast == slow) {
ListNode *ptr = head;
while (ptr != slow) {
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
}
return nullptr;
}
};
美的集团公司福利 878人发布
