寻找链表中环的入口节点

  // 寻找环的入口节点
  findRingEntranceNode(): ListNode | null {
    // 初始化两个指针指向
    this.pNext = this.listHead;
    this.pHead = this.listHead;
    let hasRing = false;
    while (this.pNext.next) {
      // p1指针每次走1步
      this.pNext = this.pNext.next;

      // p2指针每次走2步
      let step = 2;
      while (this.pHead.next) {
        if (step > 0) {
          this.pHead = this.pHead.next;
          step--;
        }
        if (step === 0) {
          break;
        }
      }
      // p1、p2相遇, 链表中就包含环
      if (this.pNext === this.pHead) {
        hasRing = true;
        break;
      }
    }

    // 链表中有环
    if (hasRing) {
      let ringCount = 0;
      // 获取环中节点数量
      while (this.pNext.next) {
        ringCount++;
        this.pNext = this.pNext.next;
        // p1、p2相遇，得到环中节点总数量
        if (this.pHead === this.pNext) {
          break;
        }
      }

      // 寻找环的入口节点
      while (this.pNext.next) {
        // 移动p1指针ringCount步
        this.pNext = this.pNext.next;
        ringCount--;
        if (ringCount === 0) {
          // 重置p2指针位置到链表头部
          this.pHead = this.listHead;
          break;
        }
      }
      // p1、p2指针以相同的速度向前移动
      while (this.pNext.next) {
        this.pNext = this.pNext.next;
        if (this.pHead.next) {
          this.pHead = this.pHead.next;
        }
        // p1、p2相遇的节点正好是环的入口节点
        if (this.pNext === this.pHead) {
          return this.pNext;
        }
      }
      return this.pNext;
    }
    // 链表中不存在环
    return null;
  }

const linkedList = new LinkedList();
linkedList.push(1);
linkedList.push(3);
linkedList.push(8);
linkedList.push(9);
linkedList.push(12);
linkedList.push(18);
// 修改最后一个节点的指针指向至链表的第3个节点，构造一个有环链表
linkedList.getElementAt(linkedList.size() - 1).next =
  linkedList.getElementAt(2);

const getLinkedListNode = new GetLinkedListNode(linkedList.getHead());
resultNode = getLinkedListNode.findRingEntranceNode();
console.log("环的入口节点", resultNode);