判环算法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

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