Linked List Cycle 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?

思路：维护两个指针slow和fast。先判断是否存在环。

在判断是否存在环时，slow每次向前移动一步，fast每次移动两步。

假设从链表头开始一共移动了K次，则fast一共移动了2K步。

两个指针在相遇时，fast一定比slow多跑了至少一个整环。设链表中环长为R，

则有2K - K = nR, 即K = nR。

再看slow所跑过的过程，设链表头到环开始的节点距离为S，环内跑了mR + D，

则有K = S + mR + D。其中，D为slow和fast相遇点在单圈内距离环起点的距离。

与上面比较得 S + mR + D = nR。进一步得 S + D = (n - m)R。

这说明了：在环内，距离环起点D处继续走S步，会得到整数倍的环长，即会回到环起点处。

而巧的是，S正好也是从链表头到环起点处的距离。

因此，我们有了解法：在判断是否存在环这一步中，当slow和fast相遇后，令slow=head，然后两个指针这次都一步一步往前走，这次两者相遇的地方就是环的起点！

算法时间复杂度O(n), 空间复杂度O(1)。

 1 class Solution {
 2 public:
 3     ListNode *detectCycle(ListNode *head) {
 4         if (head == NULL) return NULL;
 5         ListNode* slow = head;
 6         ListNode* fast = head;
 7         while (fast && fast->next)
 8         {
 9             slow = slow->next;
10             fast = fast->next->next;
11             if (fast == slow) break;
12         }
13         if (fast == NULL || fast->next == NULL)
14             return NULL;
15         slow = head;
16         while (slow != fast)
17         {
18             slow = slow->next;
19             fast = fast->next;
20         }
21         return slow;
22     }
23 };