题目链接：环形链表II
题目：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
示例1:
示例2:
- 解题过程
- 判断链表是否环
- 如有环，找到入环口的节点.
判断是否有环我已经在这一节讲过了【LeetCode】环形链表+结论证明，大家可以先去看看，这一节主要讲解如何找到入环口，与推导过程。
- 找到入环口思路
如已知道链表已经有环，那么接下来要找这个环的入口了，我们定义一个从头结点出发的指针，从链表相遇节点也同时出发一个指针，这两个指针每次移动一个节点， 那么当这两个指针相遇的时候就是环形入口的节点。
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast = head; struct ListNode* show = head; while(fast&&fast->next) { fast = fast->next->next; show = show->next; if(fast == show) { //那为什么两个指针会在入环点相遇呢？ struct ListNode* index1 = fast; struct ListNode* index2 = head; while(index1 != index2) { index1 = index1->next; index2 = index2->next; } return index1;// 返回环的入口 } } return NULL; }
- 不少人在刚开始做这题时都会有这样的疑惑，为什么两个指针会在入环点相遇呢？
- 接下来我们就推导证明一下.
有的人是这样推导的：
fast走的路程是slow的两倍
假设:
链表头节点--入环口节点的距离为-> L.
入环口节点--相遇节点距离为-> X
环的长度为->C
slow指针走的路程是: L+X 分析:(有没有可能slow进环转了几圈才追上？ 答案是：不可能，肯定是在一圈之内，fast指针必然会追上slow指针，因为他们之间距离每次缩小1，不会错过，slow走一圈，fast都走了两圈了，肯定追的上.)
fast指针走的路程是：L+X+C
推导：
2*(L+X) = L+C+X (慢指针走的路程两倍 等于 快指针的路程)
L + X = C （两边同时约定一个L+X）
L = C - X (环的距离 - 节点相遇距离 = 入环口)
该推论是错误的！！如果下面环长这样呢？
所以上面的推论只是在个别情况是正确的，那该如何推导呢？
假设：
链表头节点--入环口节点的距离为-> L.
环的长度为->C
入环口节点--相遇节点距离为-> X
fast 走的路程是： L+N*C + X
( 假设N是slow进环前，fast在环里面转的圈数 ）
推导：
2(L+X) = L+N*C + X
(两边同时约掉L+X)
L+X = N*C
L = N*C-X
所以入环点是 fast在环里面转的圈数-相遇节点距离
这也证明了从头结点出发一个指针，从相遇节点同时也出发一个指针，这两个指针每次移动一个节点， 当两指针相遇时就是 环形入口的节点。
