java实现单链表中是否有环的方法详解
这是一道微软经典笔试题,就是两个指针h1,h2都从头开始遍历单链表,h1每次向前走1步,h2每次向前走2步,如果h2碰到了null,说明环不存在;如果h2碰到本应在身后的h1说明环存在(也就是发生了套圈)。
如果环不存在,一定是h2先碰到null:
如果环存在,h2与h1一定会相遇,而且相遇的点在环内:h2比h1遍历的速度快,一定不会在开始的那段非环的链表部分相遇,所以当h1,h2都进入环后,h2每次移动都会使h2与h1之间在前进方向上的差距缩小1,最后,会使得h1和h2差距减少为0,也即相遇
package org.myorg;
public class test{
public static boolean isexsitloop(singlelist a) {
node<t> slow = a.head;
node<t> fast = a.head; while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
return true;
}
return false;
}
public static void main(string args[]){
singlelist list = new singlelist();
for(int i=0;i<100;i++){
list.add(i);
}
system.out.print(singlelist.isexistingloop(list));
}
}
package org.myorg;
public class node{
public object data; //节点存储的数据对象
public node next; //指向下一个节点的引用
public node(object value){
this.data = value;
}
public node(){
this.data = null;
this.next = null;
}
}
package org.myorg;
public class singlelist{
private int size;
private node head;
private void init(){
this.size = 0;
this.head = new node();
}
public singlelist(){
init();
}
public boolean contains(object value){
boolean flag = false;
node p = head.next;
while(p!=null){
if(value.equals(p.data)){
flag = true;
break;
}else(
p = p.next;
)
}
return flag;
}
public boolean add(object value){
if(contains(value))
return false;
else{
node p = new node(value);
p.next=head.next;
head.next = p;
size++;
}
return true;
}
}
推荐阅读