LeetCode OJ：Linked List Cycle II（循环链表II）

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

Note: Do not modify the linked list.

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

和前面那题类似，只不过这里要找到的是环开始的节点，看下面这张图(图是盗的)：

当fast以及slow指针在z处相遇的时候，可以得到一个计算式，关于两个指针走过的距离，有fast指针走过的距离是slow指针的2倍，那么有：

a + b + c + b(fast) = 2 * (a + b) => a = c;

那么从链表头在选一个指针，和slow指针一起走，正好可以在环的起始点处相遇，代码如下所示：

 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  */
 9 class Solution {
10 public:
11     ListNode *detectCycle(ListNode *head) {
12         if(!head) return NULL;
13         ListNode * slow = head;   
14         ListNode * fast = head;
15         while(slow && fast){
16             slow = slow->next;
17             fast = fast->next;
18             if(fast)
19                 fast = fast->next;
20             if(fast && slow &&fast == slow)
21                 break;
22         }
23         if(fast == NULL) return NULL;
24         ListNode * start = head;
25         while(slow != start){
26             slow = slow->next;
27             start = start->next;
28         }
29         return slow;
30     }
31 };

还有一篇博客对这个问题还有类似的衍生问题描述的比较清楚，mark一下