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

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
    // write code here
    /*
    遍历单链表的每个结点
    如果当前结点地址没有出现在set中，则存入set中
    否则，出现在set中，则当前结点就是环的入口结点
    整个单链表遍历完，若没出现在set中，则不存在环 ###代码
*/
//     let p = pHead;
//     let set = new Set();
//     while(p){
//         if(set.has(p)) return p;
//         set.add(p);
//         p = p.next
//     }
    //method 2 时间复杂度：O(n) 空间复杂度：O(1) 
    if(!pHead.next || !pHead.next.next) return null;
    let fast = pHead.next.next;
    let slow = pHead.next;

    while (fast !== slow){
        if(!fast.next || !fast.next.next) return null;
        fast = fast.next.next;
        slow = slow.next;
    }
    if(!fast || !fast.next ) return null; //注意这里检查fast.next是必要的步骤 示例2
    // fast.next 为null 没有环
    fast = pHead;
    while (fast !== slow){
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}
module.exports = {
    EntryNodeOfLoop : EntryNodeOfLoop
};