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;
    }
};