142. Linked List Cycle II

题目：

• Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
• 译文：给定一个链表，如果链表中存在环，则返回到链表中环的起始节点，如果没有环，返回null。

知识点

1. Linked List Cycle I —— 通过快慢两个指针来确定链表上是否存在环
2. 快慢指针的相遇点到环入口点的距离 = 链表起始点到环入口点的距离

扩展点

1. 快慢指针一直到相遇时的循环次数等于环的长度

循环次数 = 环的长度

• Case 1：一个完美的环状链表，即，链表的头尾相连

一个环形链表：{A，B，C，A，B，C，……}
其上存在两个指针，A指针移动速度是B指针的两倍。
A，B同时从节点1出发，所经过的节点如下：

快指针A：A->C->B->A
慢指针B：A->B->C->A

A、B指针在节点A第一次相遇，循环次数为3，而环的程度正好也为3。那这个是不是巧合呢？

首先我们要理解的是循环的次数代表的是什么。
1. 每次循环，对于B这个慢指针来说，意味着走了一个单位长度。
2. 而对于A来说，走了两个单位长度。
3. 那么二者第一次相遇必然是在A走了2圈，B走了1圈的时候。
4. 假如A的速度是B的3倍，那么二者第一次相遇是在A走了3圈，B走了1圈的时候。
5. 同理A是B的5倍速度，相遇时A走了5圈，B走了1圈
...
n. A的速度是B的n倍，相遇时A走了n圈，B走了1圈

从上面的观察我们可以发现，无论A的速度是B的几倍，两者第一次相遇必然是在B走了1圈时。
因为B的速度代表的是链表基本的长度单位，即从一个节点移动到下一个节点的距离。
同时在链表中，每个节点与节点之间这个距离是不变的。
当循环结束时，B走了1圈，正好是环的长度。而B每次移动一个单位距离，因此环的长度等于循环次数。

• Case 2：不完美的环状链表，即，链表中某一中间节点与尾部相连

  
  不完美的环形链表

一个环形链表（如图所示）：{D，E，A，B，C，A，B，C，……}
其上存在两个指针，A指针移动速度是B指针的两倍。
A，B同时从节点1出发，所经过的节点如下：

快指针A：D->A->C->B
慢指针B：D->E->A->B

根据上图，我们可以计算出A、B行走的距离：
A = d+e+a+b+c+a
B = d+e+a

因为A的速度是B的2倍，那么A行走的距离也因该是B的2倍：
d+e+a+b+c+a = 2(d+e+a)
      a+b+c = d+e+a

从上图可以看出，a+b+c正好是环的长度，而d+e+a则是B行进的距离。
又知，每次循环B移动一个单位距离，因此在不完美的环状表中，循环次数亦是等于环的长度。

相遇点到环入口点的距离 = 链表起始点到环入口点的距离

根据上文公式，我们可以继续推导，即：
a+b+c = d+e+a
  b+c = d+e

b+c是相遇点到环入口的距离
d+e是链表起点到环入口的距离

解题思路

1. 先由快慢指针检测链表上是否存在环
2. 如果环存在，根据相遇点到环入口点的距离 = 链表起始点到环入口点的距离，我们可以同时从D点（链表起始点）和B点（相遇点）循环两个指针
3. 两个会最终指向A点，即，环的起始点

/**
 * 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) {
        if(head == NULL) return NULL;
        ListNode *fast = head;
        ListNode *slow = head;
        
        while(fast != NULL && fast->next!=NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){ //快慢指针相遇，说明环存在
                //first代表着链表的起始点
                //slow代表着相遇点
                ListNode *first = head; 
                while(first != slow){//从相遇点和链表起始点同时循环两个指针，直到二者相遇，相遇点就是环起始点
                    first = first->next;
                    slow = slow->next;
                }
                return first;
            } 
        }
        return NULL;
    }
};