刷题力扣142-环形链表

题意： 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

这道题可以用哈希表做，但由于我的哈希表基础薄弱，所以先用其他方方法讲明，参考代码随想录，自己看完过程后的进一步细化。

思路：双指针法

这道题有两个难点：

1、如何判断有环；

2、如何寻找入口；

首先我们看第1问，用双指针法的话，设快慢指针，快指针一次移动两个节点，慢指针一次移动一个节点，如果不存在环只是一条直线，快慢指针永远不会有相遇的一天；如果存在环，那么快指针一定比慢指针先进入环内，且快指针至少要在环内绕一圈才能追赶上慢指针（数学的追赶问题，可以画图理解一下）。这样当fast == slow时，存在环。

再看第二问，这个就涉及到数学问题比较多了。如下图，我们设从头结点到环入口距离为x，入口到两指针相遇距离为y，相遇到入口处的距离为z，那么当两指针相遇时，慢指针走了 (x+y) ， 快指针走了 x+y+n(y+z) （n表示快指针在环内走的圈数，n >= 1）

由于快指针速度是慢指针的两倍。

2(x+y) = x+y+n(y+z)

得 x = n(y+z)-y

化简 x = (n-1)(y+z) +z

当n = 1 时，x = z ，我们可以设置俩指针index1 = head ， index2 = fast，那么当index1 = index2 时，入口处就出来了，即index1。

当n > 1时，也不难看出，无非是index2在环内多绕了几圈，但始终还是会与index1相遇的，他们相遇的地方就是入口处。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow){               //说明有环
                ListNode index1 = fast;
                ListNode index2 = head;

                while(index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }     
        }
        return null;
    }
}