题目来源：https://leetcode.cn/problems/linked-list-cycle-ii/description/

 C++题解：设置快慢两个指针，快的走两步，慢的走一步，如果没有环，快的会先指向空，返回空指针，如果有环，快慢指针就会相遇，但不知道在环的哪个位置相遇。

假设链表长度为l，环的长度为b，环之前的长度为a，a+b=l。

当快慢指针都在环内出发，快慢指针再次相遇时，快指针刚好比慢指针多走一圈（为什么只有一圈，不会跳过去？因为快指针相对，慢指针每一次都只移动一个节点，所以跳不过去。想象一下快指针在慢指针的前一个节点，两个会相遇；前两个节点，会变成前一个节点的情况），假设走了n步，那么2n-n=b。

我们要判断a的大小，那么重新设置两个前后指针，前指针先走b步，然后前后指针同时走。当前指针走了a步时，前指针走了a+b=l步，即前指针链表遍历一圈，来到了交叉点，而后指针也同时走了a步，刚好进入环节点，也就是交叉点。所以判断两个指针是否走了a步，就是判断前后指针是否再次相遇。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        //特殊情况
        if(head == nullptr) return nullptr;
        if(head->next == nullptr) return nullptr;
        else if(head->next == head) return head;

        //快指针走两步，满指针走一步，两者在环的某一节点中相遇
        slow = slow->next;
        fast = fast->next->next;
        while(fast != slow) {
            if(fast == nullptr) return nullptr;  //如果快指针指向空节点，则说明没有环
            if(fast->next == nullptr) return nullptr;
            slow = slow->next;
            fast = fast->next->next;
        }
        
        //快慢指针在环内出发，再次相遇快指针比满指针多走一圈，即环的长度=2n-n=n
        slow = slow->next;
        fast = fast->next->next;
        int n = 1;
        while(fast != slow) {
            n++;            
            slow = slow->next;
            fast = fast->next->next;
        }

        //设置前后指针，前指针先走n步，这样当前后指针再次相遇，前指针在链表末尾，后指针刚好进入环，该节点即为环的第一个节点。
        fast = head; slow = head;
        while(n--) {
            fast = fast->next;
        }
        while(fast != slow) {    
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

其实在快慢指针相遇后，假设相遇点是入环的第x个节点，即a+x+y=l，x+y=b。那么此时慢指针走了a+x，快指针（假设多走了m圈）走了a+x+mb=a+x+m(x+y)，那么2(a+x) = a+x+mb = a+x+m(x+y)，即 a = (m-1)(x+y)+y = (m-1)b+y 。

那么从相遇节点x（入环的第x个节点，实际为第a+x个节点）出发，再走a步，就相当于走了(m-1)b+y步，即x+(m-1)b+y=mb，即走回入环点。

所以可以快慢指针相遇后，跟头指针同时同速走，相遇点即为入环点。