1.jpg
2.jpg
#include <iostream>
#include <vector>
using namespace std;
struct ListNode{
int val;
ListNode* next;
ListNode(int x): val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
// 1.判断链表是否有环
while(fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
// 2.快慢指针相遇，则说明链表有环
if(fast == slow) {
ListNode* index1 = head;
ListNode* index2 = fast;
// 3.利用"快慢指针在环内相遇点处到环入口节点的距离 == 头节点到环入口节点的距离"原理,找到环的入口节点
while(index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return nullptr;
}
};
