问题

环形链表一原题链接：https://leetcode.cn/problems/linked-list-cycle?envType=study-plan-v2&envId=top-100-liked
环形链表二原题链接：https://leetcode.cn/problems/linked-list-cycle-ii?envType=study-plan-v2&envId=top-100-liked
第二题限制了不能更改原链表，且要求返回循环处的Listnode指针，还明确改进空间复杂度为O(1)，因此第二问该用快慢双指针

解法

我们先看第一题。
解法一：我们很容易想到的就是利用hash表快速辨别，显然的是如此时间复杂度和空间复杂度都不低（都O(N)）：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        //hash表解法，速度奇慢
        if(head==NULL) return false;
        unordered_map<ListNode* ,bool> mp;
        mp[head]=true;
        head=head->next;
        while(head){
            if(mp.count(head)) return true;
            mp[head]=true;
            head=head->next;
        }
        return false;
    }
};

解法二：利用快、慢双指针来优化空间复杂度为O(1)，在O(N)的时间复杂度上得到结果：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        //双指针
        if(head==NULL || head->next==NULL) return false;//不构成循环
        
        ListNode *slow=head,*fast= head->next;//为了while判断因此让fast先向前一步
        while(slow!=fast){
            if(fast==NULL || fast->next==NULL) return false;//已到尾节点,不构成循环
            slow=slow->next;
            /*核心：思路源于「Floyd 判圈算法」（又称龟兔赛跑算法），
            只要有环由于每移动一轮距离将减1，最终必然会相遇*/
            fast=fast->next->next;
        }
        return true;
    }
};

第二题，我们考虑一般情况，不妨令一条链表进入环的前部分长度为L，环的长度为C（环是首尾相连当做L=0来看待即可），slow走一步fast走两步，当slow到达环入口时，fast已走了2l，fast距离slow还差c-l的距离。因此在他两相遇时必然是fast走了2*(c-l)步，slow走了c-l步。此时slow距离入环口还差l步，由于我们不知道l的具体数值，引入新节点res，当他和slow相遇时就代表走了l步，此时他两就在入环口节点处。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow=head,*fast=head;
        while(fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast){
                ListNode *res=head;
                while(res!=slow){
                    res=res->next;
                    slow=slow->next;
                }
                return res;
            }
        }
        return NULL;
    }
};