判环算法01

判环算法01检验链表是否有环

    //判断环   public boolean hasCycle(ListNode head){       ListNode p1=head;//乌龟       ListNode p2=head;//兔子           while (p2!=null&&p2.next!=null){               p1=p1.next;               p2=p2.next.next;               if(p1==p2){                   return true;               }           }       return false;   }

思路:利用了快慢指针的原理,快的只要与慢的相遇,就代表终究是一个圆环判断环的位置02

  public ListNode hasCycle(ListNode head){       ListNode p1=head;//乌龟       ListNode p2=head;//兔子           while (p2!=null&&p2.next!=null){               p1=p1.next;               p2=p2.next.next;               if(p1==p2){//第一次遇见                  p1=head;//乌龟返回初始值                   while (true) {                       if (p1==p2) {//再次相遇                           return p1;                       }                       p1=p1.next;                       p2=p2.next;                   }               }           }       return null;   }

原理:总结规律

从起点开始走,走a+绕环n圈,都能找到环的入口位置

兔子走的:a的直线路程+绕环n圈+K

乌龟走的:a的直线路程+绕环n圈+K

兔子走的距离是乌龟的两倍

兔子走的减去乌龟走的 n

乌龟走的:兔子走的-乌龟走的=绕环圈数