Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.

Follow up:
Can you solve it without using extra space?

题意：给定链表，若是有环，则返回环开始的节点，没有则返回NULL

思路：题目分两步走，第一、判断是否有环，第二若是有，找到环的起始点。关于第一点，可以参考之前的博客 Linked list cycle。这里主要分析在有环的情况下的第二步。

说明：在环中的前进方向是顺时针，起点为X，环入口为Y，相遇点在Z；无环X->Y的距离（节点数）为a，相遇点Z到Y的距离为b，环长r。

慢指针一次走一步，即slow=slow->next；快指针一次走两步，即fast=fast->next->next。第一相遇在Z点时，slow走过的距离为a+b，fast走过的距离为a+mr+b (m>=1)，解释两个问题：一、为什么能遇到？二、为什么第一次相遇时，慢指针slow没有在环内走过n（0<n<m）圈？针对问题一，因为，快指针fast相对慢指针的的速度是1，即，可以看成，慢指针slow静止不动，而快指针fast以速度为1的情况下，在环内前行，所以能遇到。针对问题二，同样的道理，因为fast相对slow的速度是1，假设slow静止，则在fast以速度1完成一圈之前，肯定能遇到slow。

下面分析相遇时，走过的距离，即结点数。slow：a+b；fast：2*（a+b）；所以2*（a+b）=a+mr+b（m>=1）,故得到a+b=mr，即a=mr-b；所以讲slow放在X点，fast了依旧在Z点，只不过fast的速度降为1，这样，当X到Y的时候，fast也到Y，即得到环的入口点。

 /**

  * 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 *slow=head;

         ListNode *fast=head;

         //寻找第一个相遇点

         while(fast&&fast->next)

         {

             slow=slow->next;

             fast=fast->next->next;

             if(slow==fast)

                 break;

         }

         //不存在环

         if(fast==NULL||fast->next==NULL)

             return NULL;

         //存在环，slow从头开始，fast从相遇点开始单步走，再次相遇即环的开始点

         slow=head;

         while(slow !=fast)

         {

             slow=slow->next;

             fast=fast->next;

         }

         return slow;

     }

 };

//参考了Cyberspace_TechNode的博客！！！

相关问题的扩展：参考南京大乱炖

1）环的长度是多少？

方法一：从相遇点开始，让慢指针接着走，并计数，当慢指针slow和快指针再次相遇时，返回计数器的值就行

方法二：第一次相遇后，让slow,fast继续走，记录到下次相遇时循环了几次。因为当fast第二次到达Z点时，fast走了一圈，slow走了半圈，而当fast第三次到达Z点时，fast走了两圈，slow走了一圈，正好还在Z点相遇。

2）如何将有环的链表变成单链表（即解除环）？

在本题的基础上，从环的入口开始，当指针的next为环的入口结点时，令next指向NULL即可。