链表中环的入口结点

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
    // write code here
    if(!pHead){
        return null;
    }
    
    let key=0;
    let obj={};
    while(pHead){
       key = pHead.val;//节点值
       if(obj[key]){//已有节点，则有环，返回节点
           return pHead;
       }else{//没有，继续执行，数量为1
           obj[key]=1;
           pHead = pHead.next;
       }
    }
}
module.exports = {
    EntryNodeOfLoop : EntryNodeOfLoop
};

function EntryNodeOfLoop(pHead)
{
    while(pHead !== null){
        if(pHead.flag){
            return pHead
        }else{
            pHead.flag = true;
            pHead = pHead.next
        }
    }
    return null
}

function EntryNodeOfLoop(pHead)
{
    // write code here
    let fast =pHead;
    let slow =pHead;
    while(fast&&fast.next){
        fast=fast.next.next;
        slow=slow.next;
        if(fast==slow) break;
    };
    if(!fast||!fast.next) return null
    fast=pHead;
        while(fast!=slow){
        fast=fast.next;
        slow=slow.next;
    };
    return fast
}

function EntryNodeOfLoop(pHead)
{
    // write code here
    if(!pHead) return null 
    let fast = pHead, slow = pHead
    while(fast && fast.next){
        fast = fast.next.next
        slow = slow.next
        if(fast == slow){
            while(pHead !== slow){
                pHead = pHead.next
                slow = slow.next
            }
            return slow
        }
    }
    return null
}

function EntryNodeOfLoop(pHead)
{
    // write code here
    var fast = pHead,
        slow = pHead;
    while(fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow){
            break;
        }
    }
    if(!fast || !fast.next){
        return null;
    }
    fast = pHead;
    while(fast != slow){
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}

function EntryNodeOfLoop(pHead)
{
    // write code here
    if(!pHead){
        return null
    }
    let temp = pHead
    let arr = []
    while(temp){
        if(arr.includes(temp)){
            return temp
        }
        arr.push(temp)
        temp = temp.next
    }
    return null
}

1. 遍历单链表的每个结点
2. 如果当前结点地址没有出现在所定义的数组中，则存入该数组中
3. 否则，就是出现在该数组中，则当前结点就是环的入口结点
4. 整个单链表遍历完，若所有节点地址都没出现在数组中，则不存在环

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
    // write code here
    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;
}

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
    // write code here
    if(!pHead) return null;
    let nodeList = [];
    let currNode = pHead;
    while(currNode !== null){
        if(nodeList.indexOf(currNode) !== -1){
            return currNode;
        }
        nodeList.push(currNode);
        currNode = currNode.next;
    }
    return null;
}

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
    // write code here
    let tmp = {}
    let p = pHead
    while(p) {
        if(!tmp[p.val]) {
            tmp[p.val] = 1
            p = p.next
        }else {
            return p
        }
    }
    return null
}

function EntryNodeOfLoop(pHead)
{
    let h = pHead;
    if(!h.next || !h.next.next){
        return null;
    }
    let fast = h.next.next;
    let slow = h.next;
    while(fast!==null && fast.next!==null){
        if(fast === slow){
            fast = h;
            while(fast !==slow){
                fast=fast.next;
                slow=slow.next;
            }
            return slow;
        }else{
            fast = fast.next.next;
            slow = slow.next;
        }
    }
    return null;
}

    function EntryNodeOfLoop(pHead) {
      if (!pHead || !pHead.next) {
        return null;
      }
      let P1 = pHead.next;
      let P2 = pHead.next.next;
      // 1.判断是否有环
      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 = pHead;
      while (length-- > 0) {
        P2 = P2.next;
      }
      while (P1 != P2) {
        P1 = P1.next;
        P2 = P2.next;
      }
      return P1;
    }

// 题目描述：一个链表中包含环，请找出该链表的环的入口结点。

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

// 解题思路： 
// 1. 一个指针走一步，一个指针走两步，如果在到Null之前重合，则证明有环存在
// 2. 假设这个环走了若干个结点，但是由于要圈上 多走整数圈数 才能相遇，则这个等式成立 2x = x + r*n，r为圈数
// 3. 那么此时新建一个从头开始，走一步的指针，同时继续走，走x步即可回到相遇点，但是如果在相遇点之前重合，则重合点为入口
function EntryNodeOfLoop(pHead)
{
    if(!pHead || !pHead.next) {
      return null
    }
    let fast = pHead
    let slow = pHead
    // 题目已知有环
    while(1) {
      fast = fast.next
      slow = slow.next.next
      if(fast === slow) {
        break
      }
    }
    let result = pHead
    while(result !== slow) {
      slow = slow.next
      result = result.next
    }
    return result
}