题解 | #链表中环的入口结点#

  这道题很精巧，题目要求是O(1)的空间复杂度，所以不能用HashSet，只能用快慢指针。我们定义如下两个指针：

• fast: 快指针，每次向后移动两个节点

• slow: 慢指针，每次向后移动一个节点
    按照我们的定义，快指针的速度是慢指针的2倍，那么无论什么时候，快指针经过的节点数nf一定是慢指针经过的节点数ns的2倍，即等式nf = 2*ns一直成立。
    如果链表中存在环，那么由于两个节点的速度不一样，这两个指针一定会相遇。当两个指针第一次相遇时，慢指针一定在环内，而快指针肯定已经绕环转了n圈，重新到了慢指针的位置，具体绕了多少圈，如果假设环有b个节点，那么这时候快指针走过的节点数一定等于慢指针走过的节点数加上n*b，即快指针走过的节点数等于慢指针走过的节点数加上快指针绕环转了n圈走过的节点数，即n*b，不然他们也不会相遇，但n*b具体是多少我们并不确定。
    于是，在快慢指针第一次相遇时，有等式nf = ns + n*b成立，再加上nf = 2*ns，我们可以得到ns = n*b,即此时慢指针走过的节点数等于绕环走n圈经过的节点数。
    之前我们设构成环的节点数为b，这里我们再假设环之外的节点数，即链表剩余的节点数为a，那么，如果从头节点开始，想要走到环的入口节点，需要走的步数y满足y = a + k*b，k = 0,1,2...，即走完环之外的节点，再绕环走k圈就可以到达环的入口节点。快慢指针第一次相遇时，慢指针已经走了ns=n*b步，也就是说此时的k的值为n，那么慢指针再走a步就可以达到环的入口节点。如果这是我们再找一个指针从头节点开始，走a步也会到达环的入口节点，与慢指针相遇，而且相遇的地方正好是环的入口节点。于是编码如下：

  public class Solution {
  
   public ListNode EntryNodeOfLoop(ListNode pHead) {
       ListNode fast = pHead;
       ListNode slow = pHead;
       while (fast.next!=null && fast.next.next!=null) {
           /* 慢指针走一步 */
           slow = slow.next;
           /* 快指针走两步 */
           fast = fast.next.next;
           /* 如果相遇了，说明有环 */
           if (fast == slow) {
               /* 这时候我们把快指针放到头节点，让它一次走一步 */
               fast = pHead;
               /* 一直等到快慢指针相遇，这时候他们都走了 a 步，在环的入口节点相遇 */
               while (fast != slow) {
                   fast = fast.next;
                   slow = slow.next;
               }
               /* 返回结果 */
               return fast;
           }
       }
       /* 能出来就说明没有成环，直接返回 */
       return null;
   }
  }
  

```