[数据结构与算法]环形链表（快慢指针方法）

地址：142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)

?快慢指针可以判断是否存在环：

? ? ? ? 首先第一点、fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。

?判断环之后如何找到入环的第一个节点：

????????

?相遇之时可得：2*（x+y）= x+y+n(y+z) 化简的? x = (n-1)*(y+z) + z

? 由此知：假设node1节点从头开始，node2节点从相遇位置开始,node1与node2同时一步一步走，那么相遇之处即为入环之处

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        if(head == nullptr) return nullptr;
        ListNode * slow = head;
        ListNode * fast = head;
        ListNode * node1 = head;
        ListNode * node2 = head;
        int x = 1;
        while (fast && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow){
                node2 = slow;
                x = 0;
                break;
            }
        }
        if(x) return nullptr;
        while (1){
            if(node2 == node1) return node1;
            node2 = node2->next;
            node1 = node1->next;

        }
        return nullptr;
    }
};