题目

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

思路

声明两个指针 P1 P2

  • 1.判断链表是否有环: P1 P2 从头部出发,P1走两步,P2走一步,如果可以相遇,则环存在

  • 2.从环内某个节点开始计数,再回到此节点时得到链表环的长度 length

  • 3.P1、P2 回到head节点,让 P1 先走 length 步 ,当P2和P1相遇时即为链表环的起点

foo

代码

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

考察点

  • 链表
  • 程序的鲁棒性
  • 复杂问题拆解
Last Updated: 8/4/2019, 9:40:51 PM