问题：
1.给定一个链表，判断链表中是否有环。
2.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

有环链表

说明：
不允许修改给定的链表。
时间复杂度：O(n)
空间复杂度：O(1)

解决办法：
使用Floyd判圈算法，也叫龟兔赛跑算法。

原理：
设定每次兔子（快指针）跑两步，乌龟（慢指针）跑一步（这样设定是关键，也是该方法的巧妙之处），两者同时起跑。如果链表中有环，那么兔子会先进入环中，等乌龟进入环后，两者都在环内跑，所以兔子肯定会追上乌龟跟它相遇。

对于问题一，如果兔子能与乌龟相遇，就证明有环，如果兔子能跑到尽头停下来，证明没有环。

    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (true) {
        //注意判断fast是否走到尽头有两种情况，因为fast是一次跑两步的，
        //如果漏了判断fast.next是否为空，最后一次执行fast = fast.next.next时可能会报错
            if (fast == null || fast.next == null)
                return false;//跑到尽头，没有环
            slow = slow.next;//乌龟跑一步
            fast = fast.next.next;//兔子跑两步
            if(slow == fast)return true;//龟兔相遇，有环
        }
    }

对于问题二，只要在起点再放一只一次跑一步的乌龟2号，当环内的龟兔相遇时起点的乌龟2号起跑，两只乌龟相遇的位置就是环的第一个节点。原因：设乌龟跟兔子在环内相遇时乌龟共跑了x步，那么兔子就跑了2x步，兔子比乌龟多跑x步，在乌龟进入环之前，兔子已经在环内跑了n圈+c步（c>=0）,在乌龟进入环后，当兔子比乌龟跑多了一圈的步数时就追上了乌龟或者在乌龟入环时刚好相遇，所以兔子比乌龟总共多跑m+n圈（m等0或1），所以m+n圈等于x步，即x是环的长度y的整数倍（x=ky）。再设环的第一个节点离起点a步（a>=0），相遇点离环的第一个节点b步（b>=0），a+b=x=ky。当乌龟2号在起点和乌龟1号在龟兔的相遇点同时起跑时，乌龟2号走了a步，到达环的第一个节点，乌龟1号也走了a步，由于a+b是环长度的整数倍，所以乌龟1号也在环的第一个节点上，所以与乌龟2号相遇，即得到了环的第一个节点的位置。

    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(true){
            if(fast==null||fast.next==null)return null;//没有环
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)break;//龟兔相遇
        }
        while(slow!=head){
            slow=slow.next;
            head=head.next;
        }
        return slow;
    }

龟兔赛跑算法的巧妙之处在于兔子是乌龟速度的两倍，才能得到乌龟步数是环长度的整数倍的关系，从而能快速找到环的第一个节点。另外，双指针还有很多用法，不同的移动速度，不同的起点都会带来奇妙的效果。