题目描述

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

样例

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

算法思想

设置快指针与慢指针，快指针每次走俩步，慢指针每次走一步，类似环形跑道快慢相遇原理，即可证明有环，因为在直线上快慢指针永远不可能相遇。（为了确保fast是slow的俩倍,那么要保证fast走一步不能达到链表中有环的起点位置）
所以如果俩指针相遇即有环，不相遇即无环。
环起点的查询，根据数学推论可知相遇结点与初始起点，以同样的速度出发，如果俩结点相遇，则该相遇点即为环的起点。

C++ 代码

 ListNode *detectCycle(ListNode *head) {
         ListNode *fast=head;
         ListNode *slow=head;
         ListNode *meet=NULL; //初始化相遇结点
         while(fast)
         {
             fast=fast->next;
             slow=slow->next;
//为了确保俩指针到达环起点之前快指针始终是慢指针的俩倍，如果快指针走一步就达到无环链表部分的终点就不满足俩倍的设置条件，要让他走俩步才到达才满足。
             if(!fast)  
             {  return NULL; }
             fast=fast->next;
             if(fast==slow)
             {
                meet=fast; //记录相遇结点
                break;
             }
         }
           if(meet==NULL){ return NULL; } //说明无环
            //head与meeet同时出发，俩指针速度一样，相遇时即为环的起点
         while(head && meet)
         {
             if(head==meet)
             {return head;}
             head=head->next;
             meet=meet->next;
         }
         return NULL;
    }