判断链表是否有环，有环则找到入口

你的名字 2021-09-26 15:16 350阅读 0赞

设置两个指针p1,p2，p1每次走1步，p2每次走2步。  
当p2能与p1相遇，表明存在环。  
设p1走了S步，则p2走了2S步，又因为p2比p1多走了环的长度，即环的长度为L = S。  
设置头节点到入口距离为x,入口距离相遇位置为y。  
则S = x+y；  
而p2到入口距离为L - y ,即p2距离入口为x。  
因此将p1移动到头节点，然后p1每次走一步，p2每次走1步，那么二者相遇时均走了x步，即到达环入口。  
（在草稿纸上画一次相遇过程很容易理解）

public class Main { 
    
        /** * @param args */
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            ListNode a = new ListNode(1);
            ListNode b = new ListNode(2);
            ListNode c = new ListNode(3);
            ListNode d = new ListNode(4);
            ListNode e = new ListNode(5);
            ListNode f = new ListNode(6);
            ListNode g = new ListNode(7);
            ListNode h = new ListNode(8);
            a.next = b;
            b.next = c;
            c.next = d;
            d.next = e;
            e.next = f;
            f.next = g;
            g.next = h;
            h.next = d;//d为环的入口
            System.out.println(hasCycle(a));
            System.out.println(hasCycleAndGetEntry(a).val);
        }
    
         public static boolean hasCycle(ListNode head) {
             ListNode p1 = head;
             ListNode p2 = head;
             while(p2!=null){
               p1 = p1.next;
               p2 = p2.next;
               if(p2==null){
                   return false;
               }
               p2 = p2.next;
               if(p1==p2){
                   return true;
               }
            }
            return false;
       }
    
         public static ListNode hasCycleAndGetEntry(ListNode head) {
             ListNode p1 = head;
             ListNode p2 = head;
             while(p2!=null){
               p1 = p1.next;
               p2 = p2.next;
               if(p2==null){
                   return null;
               }
               p2 = p2.next;
               if(p1==p2){
                  // return true;
                   //找到环的入口
                   p1 = head ; 
                   while(p1!=p2){
                       p1 = p1.next;
                       p2 = p2.next;
                   }
                   return p1;
               }
            }
            return null;
       }
    }