给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

示例 1：

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

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分为两步，先判断链表中有没有环，再找出环的入口。另外跟链表中环的位置也有关系，分为以下三种情况：

• 没有环则返回NULL
• 纯环（循环链表），入口就是head
• 前面是单链表，后面是环

如示例1，我们假设单链表长度（节点数）为 d，环的周长为 r，快指针比慢指针快一倍，假设快慢两指针在距离环的入口 x 处相遇，则有 d+n*r+x = 2*(d+x)，得 d=n*r-x。于是分别让两指针（等速）从 head 和距离环的入口 x 处开始遍历，则一定会在环入口处相遇。

/**
 * 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 *p1=head,*p2=head;
        while(p2&&p2->next){
            p1=p1->next;
            p2=p2->next->next;
            if(p1==p2) break;
        }
        if(p2==NULL||p2->next==NULL) return NULL;
        else if(p2==head) return head;
        else p2 = head;
        while(p1!=p2){
            p1=p1->next;
            p2=p2->next;
        }
        return p1;
    }
};