判断环形链表的起点（java语言）Leetcode 142题
Leetcode 142题 判断环形链表的起点
在这里我们是使用快慢指针 (双指针) 的方式来解决此问题。
? 我们设置一个慢指针指向头结点，快指针指向头结点，快指针每次走两步，慢指针每次走一步。如果不存在环，快指针最终会指向null；如果存在环，两者最终必定在环中的某一点相遇。这是一个数学中的追击问题，两个运动员在环形跑道上匀速跑步，一个快，一个慢，慢的一方一定会被快的一方在一定时间内追上。(题外话，该论证是一个小学问题，但是我还是思考了很久，只能说智商多少沾点)，所以我们得到如何判断链表中是否存在环的条件，即快慢指针最终相遇。
? 有了判断是否存在环的条件，接下来我们在来探讨一个问题，那就是如何找到链表中环的起点。我们假设：
将带环链表拆分成一个单链和一个环，结构如下图：
? 单链的长度为a，环的长度为c，两者在环中的c点相遇，注意，这个c点是距离环的起点的单圈距离。
? 设慢指针走的路程为s，快指针走的路程是f，这里是路程，不是距离或者是位移。快指针在环上走了m圈，慢指针在环上走了n圈，所以我们能够得出：
s = a + n * b + c
f = a + m * b + c
? 同时，因为快指针每次走两步，慢指针每次走一步，两者最终相遇，那么我们可以得出： f = 2 s；
所以我们能够得出 ：a + m * b + c = 2 * ( a + n * b + c)
? 化简得 ：a + c = (m - 2n) * b
? 即 ：a + c 是 b 的整数倍，即我们从c点出发，走a步会到达环头，可能走了很多圈。
所以我们在两个快慢指针第一次相遇的时候，将慢指针再次指向头结点，快指针指向相遇的结点，两者以同样的速度（一步）前进，直至相遇，则环的起点找到。
以下是代码：java版本
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
//证明有环的方法（当然我们也可以不使用快慢指针判断是否存在环）
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
//head为空或者head只有一个结点的情况
if (fast == null || fast.next == null) {
// fast 遇到空指针说明没有环
return null;
}
// 慢指针重新指向头结点
slow = head;
// 快慢指针以相同的速率前进，直到相遇
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
本人刷题心得，如有错误和冒犯，欢迎指正。
