给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出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;
}
