参考：
http://blog.163.com/clevertanglei900@126/blog/static/1113522592011828104617420/
问题：
判断一个链表中是否有环。
分析：
我们都知道，当一个链表中没有环时，我们使用一个指针能从头遍历到尾；当链表中有环时，链表会在环中旋转。
当我们只使用一个链表指针时，可想到方法就是使用额外的数据结构来存储遍历过的每个节点，在遍历next节点时，判断next节点是否已存在于存储的节点中。
存储结构可以选择为hashTable，这样的话，总体的时间复杂度为O(n),空间复杂度为O(n)。
当我们使用两个指针时【链表操作的常用技巧！】，可以设置快、慢两个指针。
如果链表中不存在环，快指针肯定最终变为NULL；存在环的话，快指针和慢指针都会进入到环中，因为慢指针相对快指针静止，快指针相对对慢指针步伐为1，最终快指针一定能赶上慢指针。
此方法时间复杂度为O(n),空间复杂度为O(1)
更新：好友zhuoyuan 提出使用插桩法。
解答：
1）使用hashTable，在此不表。
2)使用快、慢指针。
bool isHasCycle(Node* head) const { if(head == NULL || head->next == NULL) return false; Node* slow = head; Node* fast = head->next; while(fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; if(fast == slow) return true; } return false; }
问题：
寻找一个有环链表的第一个入环节点。
分析：
1）使用hashTable存储已遍历节点的方法中，获取入环节点的时间复杂度为O(n),空间复杂度为O(n)。
2）当我们使用快慢指针时，两个节点会相遇。
假设直线阶段长度为L，两个指针的相遇点距环的起始点距离为T，这个环的长度为S。
我们让慢指针从head处开始运动，每次向前走一步；快指针从head->next处开始运动，每次向前走两步。
当两个指针相遇时，快指针旋转了m圈，慢指针旋转了n圈。
(L + m×S + T - 1) / 2 = (L + n×S + T) 【时间相同】
=> (m - 2×n)×S = T + L + 1
=> (m - 2×n - 1)×S + S - T = L + 1
显然，相遇后，让一个指针从链表起始处开始运动，另一个指针从相遇点的下一个节点开始运动。这样，两个指针会在链表的起始节点相遇。
Node* first_Node_in_cycle(Node* head) const { if(head == NULL || head->next == NULL) return false; Node* slow = head; Node* fast = head->next; while(fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; if(fast == slow) break; } fast = fast->next; slow = head; while(fast != slow) { fast = fast->next; slow = slow->next; } return fast; }
问题：
求有环链表的环的长度。
解答：
在前两问的基础之上。
1）在使用hashTable时，求解过程显而易见。
2）使用快、慢指针时，我们可以在指针相遇后，固定一个指针，然另一个指针运动。当两个指针再次相遇时，就是一圈的距离。
时间复杂度O(n)，空间复杂度O(1)。