链表中环的入口节点.md

题目描述

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

解题思路

首先要声明两个指针p1和p2

1. 判断该链表中有没有环: p1和p2从头开始出发, p1每次移动一步, p2每次移动二步,若是有环的话它们总会相遇;
2. 判断出有环存在后, 从环内的某个节点开始走, 查询出该环的长度length;
3. p1, p2都回到头部, p1先移动length步, 然后同时移动,当p1等于p2的时候即为环的入口节点.

coding

/*
* 查找出链表中环的入口节点
* params {ListNode} list
* returns {ListNode}	
*/
function entryNodeOfLoop(list) {
    if (!list || !list.next) return null
  	// 1.判断链表中是否有环
    let p1 = list.next,
        p2 = list.next.next
    while (p1 != p2) {
        if (p2 === null || p2.next === null) return null
        p1 = p1.next
        p2 = p2.next.next
    }
  	// 2.获取环的长度
    let temp = p1
    let length = 1
    p1 = p1.next
    while (temp != p1) {
        p1 = p1.next
        length++
    }
  	// 3.查询入口节点
    p1 = p2 = list
    while (length-- > 0) {
        p1 = p1.next
    }
    while (p1 != p2) {
        p1 = p1.next
        p2 = p2.next
    }
    return p1
}