java——单链表的环
思路：
如果单链表有环，可以设一个快指针first每次走两步，慢指针last每次走一步，每走一次都要比较，当first与last两个指针相遇的时候，慢指针last肯定没有遍历完链表，而快指针已经在环内循环了n圈，假设慢指针last走了s步，那么快指针因为慢指针每次走一步它走两步，也就是first走了2s步：
/**
* 创建环
*/
public void setUpLoop() {
Entry cur = head;
while( cur.next != null) {
cur = cur.next;
}
cur.next = head.next.next.next;
}
/**
* 判断环，设置两个引用，其中一个引用一次走两步，一个一次走一步，
* 如果两个引用在某一位置相遇，则说明有环
* @return
*/
public boolean judge() {
Entry first = head;
Entry last = head;
while(first != null && first.next != null) {
first = first.next.next;
last = last.next;
if(first == last) {
return true;
}
}
return false;
}
/**
* 获得环的入口节点，因为快引用是慢引用的两倍，可以得到在相遇的时候，
* 将某一个引用放到链表的头，然后两个指针都开始一步一步的走，当他们
* 再次相遇的时候就是环的入口点了。
* @return
*/
public int obtainEntrance() {
if(!judge()) {
return -1;
}
Entry first = head;
Entry last = head;
while(first != null && first.next != null) {
first = first.next.next;
last = last.next;
if(first == last) {
break;
}
}
first = head;
while(first != last) {
first = first.next;
last = last.next;
}
return first.data;
}
/**
* 求环的长度,方法1
* @return
*/
public int getLoopLength1(){
if(!judge()) {
return -1;
}
boolean tag = false;
Entry fast = head;
Entry slow = head;
int count=0;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow&&tag==true)
break;
if(fast==slow&&tag ==false)
tag=true;
if(tag=true)
count++;
}
return count;
}
/**
* 求环的长度,方法2
* @return
*/
public int getLoopLength2() {
if(!judge()) {
return -1;
}
Entry first = head;
Entry last = head;
while(first != null && first.next != null) {
first = first.next.next;
last = last.next;
if(first == last) {
break;
}
}
last = last.next;
int len = 1;
while(first != last ) {
last = last.next;
len++;
}
return len;
}