链表中环的入口节点

发表于 | 分类于

题目

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

思路

快慢指针

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function EntryNodeOfLoop(pHead) {
  let fast = pHead;
  let slow = pHead;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (fast === slow) {
      // 两者相遇
      let p = pHead;
      while (p !== slow) {
        p = p.next;
        slow = slow.next;
      }
      return p;
    }
  }
  return null;
}