给定一个链表,判断链表中是否有环。
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
int i = 1;
while(fast != null ){
i = -i;
if(i>0){
slow = slow.next;
}
fast = fast.next;
if(slow == fast){
return true;
}
}
return false;
}
}
使两个指针同时从头结点出发,快指针每一次循环都往下走一步,慢指针隔一次走一步,成环后由于两个指针会打转,两个指针步长一致,快的一定会追上慢的,并且在同一个节点上;