在时间复杂度为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);
}
}
