剑指offer-js 链表中环的入口节点

链表中环的入口节点

相似推荐

判断链表中有无环
判断是否有环并返回入口节点(java)

题目描述：

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

问题分析：

两种方法：
	1，哈希表法
		创建一个数组，遍历所有链表元素，判断是否在数组内，若不在，则加入；若在，就将第一个在的节点返回
		
	2，快慢指针，floyd算法
		借用两张官方解法放出的图片

第一张图告诉我们，对于快慢指针，当slow和fast相遇时，相遇点在C,	同时推导出 =>2(AB+BC) = AB+BC+CB+BC	=> AB = CB

第二张图告诉我们，当slow走到入口节点B的时候，fast走到D,也就是说 => 2AB = AB+BC+CD =>AB = BC+CD
结合上图的结论  AB = CB	则可以推导出 => CB = BC+CD =>CD+DB = BC+CD => DB=BC	也就是为什么 BC,BD两个距离都是Y

所以根据 X,Y 距离的设置  结合之前的关系（AB = CB） 推导出 => CD = X-Y,CDB=X
然后，当slow和fast在C点相遇后，让slow指针的位置不变，也就是指向C,更改fast指针的指向为pHead,两个指针每次都走一步，下一次相遇就是入口节点

代码展示：

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
    //2,哈希表
    if(pHead === null || pHead.next === null)
        return null;
    let res = [];
    let node = pHead;
    while(node !== null){
        if(res.indexOf(node)>-1)
            return node;
        res.push(node);
        node = node.next;
    }
    return null;
    
    // 1，快慢指针 floyd算法
    //  a,找相遇点 b,找入口
    if(pHead === null || pHead.next === null)
        return null;
    let slow = pHead;
    let fast = pHead;
    while(fast !== null && fast.next !== null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast)//此时两节点相遇
            break;
            //return slow;
    }
    //更改fast指向为pHead
    fast = pHead;
    while(slow !== fast){	//下一次相遇就是入口节点
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}