1:三个基本的问题点
1.单链表是否有环？
2.有则输出环的长度？
3.找到环的入口节点？
分析：
定义两个指针fast 和slow，fast每次向后移动两个节点，slow每次想后移动一个节点。
1.如果没有环，则fast首先到达链表结尾；
2.链表有环的情况下：fast与slow两次相遇，slow中间走过的节点处即为环的长度；
3.找环的入口节点稍微复杂点，有如下的推导过程：
相遇的时候，slow共移动了s步，fast共移动了2s步。
定义a如下： 链表头移动a步到达入口点。
定义x如下： 入口点移动x步到达相遇点。
定义r如下： 环的长度。
定义L如下： 链表总长度为L。
其中Ｌ ＝ a + r
那么slow和fast相遇了，fast必然比slow多走了n个圈，也就是 nr 步，那么
s = a + x
2s = s + nr ， 可得 s = nr
将s=a+x，带入s =nr，可得 a+x = nr, 也就是 a+x = (n-1)r + r
从表头移动到入口点，再从入口点移动到相遇点，也就是移动了整个链表的距离，即是 L = a + r , 所以r = L - a
所以 a+x = (n-1)r + L - a , 于是 a = (n-1)r + L - a - x
得到：从表头到入口点的距离，等于从相遇点到入口点的距离。
所以，从表头设立一个指针，从相遇点设立一个指针，两个同时移动，必然能够在入口点相遇，这样，就求出了相遇点。
2:实现方式
2.1：判断是否存在环
private static boolean hasCircleNode(Node head) {
if (head == null) {
return false;
}
Node fast = head;
Node slow = head;
while (fast != null && fast.getNext() != null) {
fast = fast.next.next;
slow = slow.next;
if (slow.value == fast.value) {
return true;
}
}
return false;
}
2.2:环的长度
public static void circleLength(Node head) {
if (head == null) {
return ;
}
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
int len = 1;
fast = fast.next.next;
slow = slow.next;
while (fast != slow) {
len++;
fast = fast.next.next;
slow = slow.next;
}
System.out.println("circle length==" + len);
}
}
}
2.3:环的入口
public static void circleLength(Node head) {
if (head == null) {
return ;
}
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
int len = 1;
fast = fast.next.next;
slow = slow.next;
while (fast != slow) {
len++;
fast = fast.next.next;
slow = slow.next;
}
System.out.println("circle length==" + len);
fast = head;------------>输出环入口节点
while (fast != slow) {
fast= fast.next;
slow = slow.next;
}
System.out.println("circle point==" + slow.value);
}
}
}
