LeetCode刷题 #142 环形链表Ⅱ ( 返回链表开始入环的第一个节点)

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意 pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

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

示例1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

思路：
首先，找到快慢指针的交汇处；
然后，运用数学中推导的公式，我们可以知道他们俩交点的位置到入环节点的距离，和链表第一个节点到入环节点的距离，是相等的。利用这一条件来循环找出入环节点。

示意图：

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) {
            break;
        }
    }
// 跳出循环有两种可能，一种是不带环到末尾了
    if (fast == null || fast.next == null) {
        return null;
    }
// 一种是找到了快慢指针的交点，
// 设置两个引用
// 一个从链表第一个位置开始遍历，一个从交点位置开始遍历
// 他们会同时到达入环点，所以当他们相等时，返回相等点的引用。
    ListNode cur1 = head;
    ListNode cur2 = fast;
    while (cur1 != cur2) {
        cur1 = cur1.next;
        cur2 = cur2.next;
    }
    return cur1;
}