55.链表中环的入口节点

题目描述：

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

知识点：

• 双指针遍历链表

解题思路：

• 这道题是判断链表中是否有环的升级版
• 在判断链表中是否有环的问题中我们采用一快一慢两个指针来遍历整个链表，当两个指针相遇说明有环
• 而在这道题中我们需要记录这个环节点
• 在找到这个环节点后我们让一个指针从链表的头部再次同之前相遇的节点一起往前走
• 当两指针再次相遇返回当前节点便好
• 具体原因这道题还是看图比较方便，大家可以参考一下链接这个人的题解可能会更容易理解

解题代码：

function EntryNodeOfLoop(pHead)
{
    // write code here
    if(!pHead || !pHead.next) return null; // 注意这里还存在只有一个节点的情况
    let fast = pHead;
    let slow = pHead;
    while(fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        if(slow === fast) { // 注意：初始指针指向同一个节点，所以这里一定是先移动指针再判断的
            break;
        }
    }
    if(!fast) return null; // 注意：这里一定要判断一下当前节点是否为空，解决如果没有环的问题
    let p = pHead;
    while (slow) {
        if(slow === p) { // 这里是先判断再移动指针
            return p;
        }
        p = p.next;
        slow = slow.next;
    }
    return null;
}