题目描述:
Given a linked list, return the node .where the cycle begins. If there is no cycle, return null.Follow up:Can you solve it without using extra space?
1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
思路1：
先求出环中的节点个数n，然后先让快指针先走n步。然后快慢指针一起走。
1 class Solution {
2 public:
3 ListNode *detectCycle(ListNode *head) {
4
5 if(head==nullptr || head->next==nullptr)
6 return nullptr;
7 ListNode *fast = head;
8 ListNode *slow = head;
9 //这个循环的主要目的是为了判断是否存在环
10 while(fast->next && fast->next->next)//不是环的话，会遇到nullptr结点
11 {
12 fast = fast->next->next;
13 slow = slow->next;
14 if(fast == slow)//是环的话，快慢指针会相遇
15 break;
16 }
17 //好的编程习惯：当循环中有好几处能使循环中断的情况，循环中断后，
18 //应该首先判断是那种情况引起的循环中断
19 if(fast->next==nullptr || fast->next->next==nullptr)
20 return nullptr;
21 fast = fast->next;
22 int cnt = 1;//cnt为环的节点个数，也即从环中一个结点出发又回到原地需要移动的次数
23 while(fast != slow)
24 {
25 fast = fast->next;
26 ++cnt;//每移动一次cnt的状态更新一次
27 }
28 fast = head;
29 slow = head;
30 for(int i = 0; i < cnt; ++i)
31 fast = fast->next;
32 while(slow != fast)
33 {
34 slow = slow->next;
35 fast = fast->next;
36 }
37 return slow;
38 }
39 };
思路2：
如下图所示，X,Y,Z分别为链表起始位置，环开始位置和两指针相遇位置，则根据快指针速度为慢指针速度的两倍，可以得出：
2*(a + b) = a + b + n * (b + c)；即a=(n - 1) * b + n * c = (n - 1)(b + c) +c;注意到b+c恰好为环的长度，故可以推出，如将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。故两指针会在环开始位置相遇。
代码：
1 class Solution {
2 public:
3 ListNode *detectCycle(ListNode *head) {
4
5 if(head==nullptr || head->next==nullptr)
6 return nullptr;
7 ListNode *fast = head;
8 ListNode *slow = head;
9 //这个循环条件只是为了保证循环的进行，如果一个链表中前进能
10 //遇到nullptr结点，则一定不是环,用fast->next->next!=nullptr只是
11 //为了如果不是环的话及早发现，没有什么
12 //换成while(fast && fast->next)也可以，不过这样的话，不是环的话
13 //得多进行一个循环次数
14 while(fast->next && fast->next->next)//不是环的话，会遇到nullptr结点
15 {
16 fast = fast->next->next;
17 slow = slow->next;
18 if(fast == slow)//是环的话，快慢指针会相遇
19 break;
20 }
21 //好的编程习惯：当循环中有好几处能使循环中断的情况，循环中断后，
22 //应该首先判断是那种情况引起的循环中断
23 if(fast->next==nullptr || fast->next->next==nullptr)
24 return nullptr;
25 slow = head;
26 while(slow != fast)
27 {
28 slow = slow->next;
29 fast = fast->next;
30 }
31 return slow;
32 }
33 };
原文：https://www.cnblogs.com/zjuhaohaoxuexi/p/11772215.html