链表环的入口节点

题目

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

思路

声明两个指针 P1 P2

1.判断链表是否有环： P1 P2 从头部出发，P1走两步，P2走一步，如果可以相遇，则环存在 2.从环内某个节点开始计数，再回到此节点时得到链表环的长度 length 3.P1、P2 回到head节点，让 P1 先走 length 步 ，当P2和P1相遇时即为链表环的起点

代码

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;
}

考察点

• 链表
• 程序的鲁棒性
• 复杂问题拆解