思路
声明一个快指针、一个慢指针,快指针一次走两步,慢指针一次走一步。如果快慢两个指针相遇,说明链表有环。
至于为什么快慢两个指针相遇就说明链表中有环,这个牵扯到数学证明。这里就不论证了,我们直接用结论。
代码实现
初始化的时候,快指针指向 head.next
,慢指针指向head。
public static boolean checkCircle(Node head) {
if(head == null){ return false;}
Node fast = head.next;
Node slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast)
return true;
}
return false;
}