链表经典问题之环形链表
- 环形链表追及问题：为什么有环链表快指针一定可以与慢指针相遇？
证明：进入环后，假设慢指针距离快指针n步，fast每次走2步，slow每次走1步，每次走完后他们的距离将缩短1步。
如下，到最后距离总会变成0，即会相遇。n n-1 n-2 n-3 ... 0
-
扩展：第一次进入环后，假设慢指针距离快指针n步，fast每次走3步，slow每次走1步，每次走完后他们的距离将缩短2步。这种情况下是否会相遇？
分2种情况偶数 奇数 n n n-2 n-2 n-4 n-4 ... ... 2 1 0 -1
-
距离为偶数的情况下最终距离还是0，与上面的情况相同，依然能相遇；
-
距离为奇数的情况比较复杂，还取决于环的大小。最后距离为-1，可以理解为：新的一圈的大小减1的距离 ，即C-1（画图可助于理解）
- 此时若C-1为奇数，则陷入奇数的死循环，即永远不会相遇；
- 此时若C-1为偶数，则进入偶数的循环，最终距离变0，相遇。
-
- 这次的问题还需要返回相遇的位置pos
解题思路： 如果链表存在环，则fast和slow会在环内相遇，定义相遇点到入口点的距离为X, 定义环的长度为C,定义头到入口的距离为L,fast在slow进入环之后一圈内追上slow,则会得知： slow所走的步数为:L + X fast所走的步数为：L + X + N * C 并且fast所走的步数为slow的两倍， 故： 2*(L + X) = L + X + N * C 即： L = N * C - X 所以从相遇点开始slow继续走，让一个指针从头开始走，相遇点即为入口节点
详解：
假设快指针与慢指针已相遇，此时慢指针在环外已走过L，环内走过X，环长假设为C。所以
slow的路程为：L+X
而fast必定至少走完一圈，那这里能否设fast距离为L+X+C 呢？
答案是否定的，因为当环非常小的时候，fast可能在环已走过N圈，而不只有1圈。因此
fast的路程为：L+X+N*C(N 为fast在环里走过的圈数)
而又有fast的路程=2倍的slow路程=2*(L+X)，结合等式可推导出L
fast_S = L+X+N*C =2*(L+X) L=N*C-X 这里对右边变形 L=(N-1)*C+(C-X)
对这个结果的理解：一个结点从头节点往后走，一个结点从相遇结点往后走若干圈回到原点，再走C-X步，则一定回到环的起点。
即只要头节点head和相遇结点meet一步一步往后走，必定会在L处相遇。
代码
public ListNode detectCycle(ListNode head) {
ListNode fast,slow;
fast=slow=head;
while(fast!=null&&fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
if(fast==slow){
ListNode meet=fast;
while(meet!=head)
{
meet=meet.next;
head=head.next;
}
return meet;
}
}
//无环
return null;
}
