链表|链表 - 判断链表是否有环以及环的入口链表-判断链表是否有环以及环

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

一. 什么是链表的环？ 【链表|链表 - 判断链表是否有环以及环的入口】单链表出现循环的情况就是链表的环。
所以，寻找环的入口就是找到循环开始的地方。
二. 解决方案

快慢指针
- 理解该方法需要我们推导一条原理
  文章图片
- 如图所示，x为链表入口到环入口的距离，y为环入口到快慢指针相遇点的距离，z为相遇点到环入口的距离。
- 同时，环的总长度为L，即L = y + z。
- 设置快指针，每次走2个节点，记为2S。
- 设置慢指针，每次走1个节点，记为1S。
  
  文章图片
- 化简得到：x = (n - 1)L + z 。
- 其中n是快指针比慢指针多走的循环数，当n = 1时，x = z，也就是说，当快指针只比慢指针多走一圈就相遇的话，链表入口到环入口的距离=相遇点到环入口的距离。当n != 1 时，道理一样，只不过快指针跑多几圈而已。
- 正是基于上面的结论，可以在快慢指针第一次相遇的地方重置快指针的位置，使快指针回到链表入口，慢指针不动。然后，两个指针以相同的速度在运动，再次相遇的地方就是环入口。

function EntryNodeOfLoop(pHead) { let fast = pHead; let slow = pHead; while(fast && fast.next){ fast = fast.next.next; // 快指针一次走两步 slow = slow.next; // 慢指针一次走一步 if(fast == slow){ // 第一次相遇重置快指针的位置以及速度 fast = pHead; while(fast != slow){ fast = fast.next; slow = slow.next; } return fast; // 再次相遇的地方就是环入口 } } return null; }