java完成單鏈表中能否有環的辦法詳解。本站提示廣大學習愛好者：（java完成單鏈表中能否有環的辦法詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是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;
}
}
