链表中的入口结点

判断一个链表是否存在环，有一个Floyd判圈法

tortoise = top
hare = top

forever:
     if hare == end :
         return 'No Loop Found'
     hare = hare.next

     if hare == end :
         return 'No Loop Found'
     hare = hare.next

     tortoise = tortoise.next

     if hare == tortoise:
         return 'Loop Found'

这里的快慢指针分别用hare和tortoise来指代。

判定存在圈的条件是快慢指针重合，也就是上图中的乌龟和兔子能够走到一起去。
而本题我们要求返回这个链表环的入口结点。

网上的好多回答都是基于列未知数方程判定关系，如果在面试的过程中让我现场第一次推算这个过程（现在是会了，也是做的次数多了才记住了）我是不行的，必须得找到一个更加容易理解的方式。

这里我把环展开，让乌龟和兔子在展开的路上跑，兔子的速度是乌龟的二倍。

红色的代表环，分割线分割重复的环，也就是他们多跑一个环我就多展开一个，上图显示的就是他们所跑的真正路程。当乌龟距离入口的距离与兔子距离入口的距离相同的时候，他们就算是相遇了。

而且兔子跑的总路程应该是乌龟的二倍。

这时候我们派出另一只红色乌龟从头开始跑，当这红色只乌龟跑完a-b的路程的时候，绿色乌龟也跑到了a-b到达环的入口处了。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null) {
            slow = slow.next;
            if(fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            if(fast == slow) {
                ListNode node = head;
                while(node != slow) {
                    node = node.next;
                    slow = slow.next;
                }
                return node;
            }
        }
        return null;
    }
}