141. 环形链表

1. 题目描述

(题目来源：领扣 https://leetcode-cn.com/problems/linked-list-cycle/)

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

2. 快慢指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        //快慢指针
        if(head == nullptr || head->next == nullptr){
            return false;
        }
        auto slow = head;
        auto fast = head->next;
        while(slow != fast){
            if(fast == nullptr || fast->next == nullptr){
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

3. 升级：确定入环点的位置

（题目来源：领扣 https://leetcode-cn.com/problems/linked-list-cycle-ii/）

题解参照领扣官方解答

关键信息：

1) 快慢指针一定在慢指针第一次入环后相遇

2) 相遇点到入环点的距离==头结点到入环点的距离

Step1：如图所示，设链表中环外部分的长度为 a, slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。

Step2：任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有a+(n+1)b+nc=2(a+b)⟹a=c+(n-1)(b+c)

Step3：证明“快慢指针一定在慢指针第一次入环后相遇，即 n=1”，。。。不知道怎么证明了，看领扣评论区^_ ^_

4. 代码

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr){
            return nullptr;
        }
        //快慢指针一定在慢指针第一圈没走完时相遇
        ListNode *slow = head, *fast = head;
        while(fast){
            if(fast->next == nullptr){
                return nullptr;
            }
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast){
                ListNode *ptr = head;
                while(ptr != slow){
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};