环形链表求入口点_计算环形链表的入口

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

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

看到这道题，我们首先应该想到的是判断这个链表是否有环，如果有环，找到入口点，否则返回true。

怎么判断链表是否有环呢？

指定一个快指针和慢指针，快指针一次走两步，慢指针一次走一步。

如果没有环，快指针一定会遇到null；

如果有环，在经过一段时间后，快指针一定会和慢指针相遇。

 如果链表是有环的，怎么找到环的入口点呢？

这需要推导一些公式：

如图，这是一个环形链表，我们假设链表的起始点到环的入口点的距离为L，环的周长为R，环的入口点到快慢指针的相遇位置的距离为X（图中红色箭头标注的就是快慢指针的相遇点）。

快指针走的距离：F = L+X+n*R

慢指针走的距离：S = L+X

注意：慢指针一定是走不到一圈就相遇了，因为如果在环的入口点没有相遇的话，快指针的速度是慢指针的两倍，慢指针在入口点时快指针已经进入环内，在慢指针走完一圈之前，快指针一定会追上它。最差的情况就是在入口点相遇，这是快指针走了两圈，慢指针刚好走了一圈，这个情况后面再讨论。

因为快指针走的距离是慢指针的两倍，所以F = 2*S。

这时：L+X+n*R = 2 * (L + X)

          L = n*R - X

当n = 1时，也就是快指针走了一圈之后，在第二圈的时候遇见了慢指针，L = R - X

我们可以发现，L是链表的表头到环的入口点的位置，(R - X)是相遇点到环入口点的位置。

现在已经有办法得到环的入口点了，但是不要忘记一个特例：

如果链表的表头就是环的入口点呢？

我们可以发现，如果链表的表头就是入口点，使用快慢指针的时候，因为快指针是慢指针的速度的2倍，所以它们一定是慢指针走了一圈，快指针走了两圈的时候相遇，就是在环的入口点相遇。

所有的情况都已经考虑到了，这时就可以想办法算入口点了。

我们现在已经知道了相遇的位置，这时另外添加一个变量tmp指向头结点，tmp走一步，快指针（或者慢指针）走一步，当它们两相遇的时候，就是环的入口点。在这里也不要忘记特殊情况：如果相遇点等于头结点，那么头结点一定就是环的入口点。

这时就可以动手写代码了：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if((head == null) || (head.next == null)){
            return null;
        }
        //使用快慢指针，若有环，相遇，否则无环
        ListNode fast = head;
        ListNode slow = head;
        while((fast != null) && (fast.next != null)){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                //有环
                //记住相遇点的指针，一个从相遇点开始，一个从头开始，相遇的地方就是环的入口点
                ListNode tmp = head;
                //假设链表的开始就是入口点
                //如果链表的开始是入口点，最后一定在开始的位置相遇
                //因为fast是slow的两倍，当fast走了一圈的时候,slow走半圈，最后在fast走两圈，slow走一圈的位置相遇
                if(tmp == fast){
                    return fast;
                }
                while(true){
                    fast = fast.next;
                    tmp = tmp.next;
                    if(fast == tmp){
                       break;
                    }
                }
                return fast;
            }
        }
        return null;
    }
}