算法題之判斷單鏈表是否有環(huán)
判斷單鏈表是否有環(huán)的算法核心思想是用兩個指針运授，一個走的慢荧关，一個走得快咏尝，如果兩個相遇了則代表有環(huán)压语，如果不相遇則代表無環(huán)啸罢。這里可以定義第一個指針每次走一步，第二個指針每次走兩步胎食，這樣便可以判斷單鏈表中是否有環(huán)扰才。
class Node{
int val;
Node next;
public Node(int val){
this.val =val;
}
}
public class LinkedLoop {
public static boolean hasLoop(Node head){
Node p1 = head;
Node p2 = head;
while(p2!=null&&p2.next!=null){
p1=p1.next;
p2=p2.next.next;
if(p2==null)
return false;
if(p1.val==p2.val)
return true;
}
return false;
}
public static void main(String[] args){
Node n1 = new Node(1);
Node n2 = new Node(3);
Node n3 = new Node(6);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(10);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n5;
System.out.println(hasLoop(n1));
}
}
