检测链表中是否有环

在时间复杂度为O(n)、空间复杂度为O(1)的情况下，检测单向链表中是否存在环。

可以类比于操场跑步。假设两个人A、B在操场上跑步，A的速度是10，B的速度是20，两人同时从起点出发，会在起点再次相遇。利用这一点可证，用两个指针以不同的速度向后移动，如果存在环，它们一定会相遇，且满足时间复杂度和空间复杂度要求。

实现代码如下

//Node Class
package LinkList;

public class Node {
    public int val;
    public Node next;
    
    public Node() {
        // TODO Auto-generated constructor stub
        this.val = new Integer(-1);
        this.next = null;
    }
    
}

//main
import LinkList.Node;

public class Main {
    public boolean hasRing(Node head) {
        Node fast,slow;
        fast = slow = head;
        while (head.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast==slow) {
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        Node node[];
        node = new Node[10];
        for (int i = 0; i < node.length; i++) {
            node[i] = new Node();
        }
        for(int i=0;i<9;i++){
            node[i].val = i;
            node[i].next = node[i+1];
        }
        node[9].next = node[7];
        node[9].val = 9;
        
        for (int i = 0; i < node.length; i++) {
            System.out.println(node[i].val + ":" + node[i].next.val);
        }
        
        boolean hasRing = new Main().hasRing(node[0]);
        System.out.println("是否存在环"+":"+hasRing);
    }

}