JZ23 链表中环的入口结点

描述

给一个长度为n链表               ，若其中包含环  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 ，请找出该链表的环的入口结点















，否则
  
  
  
  
  
  
  
 ，返回null
  
  
  
  
  
  
  
  。

解析

环很大 在前面我们提到过快慢指针  
  
  
  
  
  
  
  ，判断是否有环 
  
  
  
  
  
  
  
。如果有环
 


 


 


 


 


 


 


 

，在来找环的入口 


 


 


 


 


 


 


 

。如果没环直接返回null即可
 
 
 
 
 
 
 
，我们假设是有环的   
   
   
   
   
   
   
   ，那么会有两种情况
 

 

 

 

 

 

 

 
，一种是O型

 

 

 

 

 

 

 

，一种是6型                ，其实原理都一样
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 ，这里主要看一下6字型的环















，他会有两种情况                       ， 如果有环 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，那么快指针走过的路径就是图中a+b+c+b























，慢指针走过的路径就是图中a+b               ，因为在相同的时间内  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 ，快指针走过的路径是慢指针的2倍















，所以这里有a+b+c+b=2*(a+b)
  
  
  
  
  
  
  
 ，整理得到a=c 在相遇的时候再使用两个指针  
  
  
  
  
  
  
  ，一个从链表起始点开始
 


 


 


 


 


 


 


 

，一个从相遇点开始
 
 
 
 
 
 
 
，每次他们都走一步   
   
   
   
   
   
   
   ，直到再次相遇
 

 

 

 

 

 

 

 
，那么这个相遇点就是环的入口
 
 
 
 
 
 
 
 。 环很小 这种情况下当快慢指针在环上相遇的时候

 

 

 

 

 

 

 

，快指针有可能在环上转了好几圈                ，我们假设相遇的时候快指针已经在环上转了n圈  
   
   
   
   
   
   
   
。 那么相遇的时候快指针走过的路径就是a+b+(b+c)*n
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 ，（b+c其实就是环的长度）















，慢指针走过的路径是a+b 

 

 

 

 

 

 

 
。由于相同时间内快指针走过的路径是慢指针的2倍

 

 

 

 

 

 

 

 。 所以有a+b+(b+c)n=2(a+b)                       ，整理得到a+b=n*(b+c) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，也就是说a+b等于n个环的长度               。 我们还可以使用两个指针























，一个从链表的起点开始               ，一个从相遇点开始  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 ，那么就会出现一种情况就是















，一个指针在路径a上走
  
  
  
  
  
  
  
 ，一个指针一直在环上转圈  
  
  
  
  
  
  
  ，最终会走到第一种情况 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 
。

代码

package mid.JZ23链表中环的入口结点; class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode slow = hasCycle(pHead); if (slow == null) return null; //快的回到起点 ListNode fast = pHead; while(fast != slow) { fast = fast.next; slow = slow.next; } return fast; } /** * 判断链表是否有环 * @param head * @return */ public ListNode hasCycle(ListNode head) { if (head == null) return null; ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) { //快的走两步 fast = fast.next.next; //慢的走一步 slow = slow.next; //如果相同返回慢的指针 if (fast == slow) return slow; } return null; } }