算法题之判断单链表是否有环
判断单链表是否有环的算法核心思想是用两个指针，一个走的慢，一个走得快，如果两个相遇了则代表有环，如果不相遇则代表无环。这里可以定义第一个指针每次走一步，第二个指针每次走两步，这样便可以判断单链表中是否有环。
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));
}
}
