题目

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

方法

方法一：双指针：https://blog.csdn.net/snow_7/article/details/52181049
方法二 —— 断链法：https://blog.csdn.net/gatieme/article/details/51602910

思路

方法二断链法会修改链表指向，而且只适用于链表中一定有环的情况找出环的入口结点，所以我们这题
暂不讨论断链法

针对双指针，方法是初始化两个指针，快速指针fast，慢速指针slow，均指向链表的头部
两个指针一起移动，快速指针的步长是2，每次向前移动2个节点，slow指针的步长为1
因为存在环，所以fast指针会在某个时刻重新追上slow指针，此时fast比slow多走了一个环的长度
假设链表长度n = l + m，其中m是环节点数量，fast指针走的距离为2x，slow走的距离为x
那么由上面的分析可知，2x - x = m，又因为2x - x = x，所以x = m
那么slow指针再走l就可以到达链表尾部节点的下一个节点，也就是环的入口
但是我们不知道l的长度，所以此时我们新建一个指针p指向头部，因为l就是链表中环之外的长度，所以只要p和slow指针，一起以步长为1移动，等两个指针指向同一个节点的时候，该节点就是环的入口节点

代码

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop (pHead) {
  // write code here
  if (!pHead || !pHead.next) return null
  let single = pHead
  let double = pHead
  do {
    single = single.next
    double = double.next.next
    if (single === double) {
      let p1 = single
      let p2 = pHead
      while (p1 !== p2) {
        p1 = p1.next
        p2 = p2.next
      }
      return p1
    }
  } while (single && double)
  return null
}