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.判斷鏈表是否有環(huán)
        while(fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            // 2.快慢指針相遇，則說(shuō)明鏈表有環(huán)
            if(fast == slow) {
                ListNode* index1 = head;
                ListNode* index2 = fast;
                // 3.利用"快慢指針在環(huán)內(nèi)相遇點(diǎn)處到環(huán)入口節(jié)點(diǎn)的距離 == 頭節(jié)點(diǎn)到環(huán)入口節(jié)點(diǎn)的距離"原理,找到環(huán)的入口節(jié)點(diǎn)
                while(index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return nullptr;
    }
};