LeetCode 141.环形链表 C写法

LeetCode 141.环形链表 C写法

思路🧐：

​ 利用快慢指针，快指针走两步，慢指针走一步，如果没有环，快指针走完就返回false，如果有环，那么快指针一定先进环，等慢指针进环以后快指针对慢指针进行追击。

​ 慢指针进环以后，每一次循环快指针与慢指针的距离都会缩短一步，直到与慢指针相遇，此时就能判断该链表带环。

​ 不过这仅是快指针走两步的情况，假设快指针与刚进环的慢指针距离设为n，快指针走三步，慢指针走一步，那么每次循环后距离为n-2，n为偶数则能整除2，也会相遇，但n为奇数的话，n则无法整除2，最后一定会错过，进入新的一轮追击。如果环的长度为C，此时快指针与慢指针距离为C-1，若C-1也为奇数的话，那将永远遇不上。

代码🔎：

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next) //如果为空则说明没环
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow) //相遇则带环
            return true;
    }
    return false;
}