【Daily Interview】- 13 环形链表Ⅱ

题目

!! 题目来源：环形链表Ⅱ - 力扣

分析

前面已经做过基础的环形链表了，感兴趣的读者可以去看看这一篇：环形链表。

这里对环形链表不再赘述，接下来分析题目：在判断链表是否是环形之余，还需要找到入口节点。

何为入口节点？

看看下图就明白了：

这里的 3 就是环的入口节点。

明白了这点，那么题目其实已经比较好解了：当我们找到重合的第一个节点的时候，显然就是入口节点了。

var detectCycle = function (head) {
  const cache = new Set();
  while (head) {
    if (cache.has(head)) {
      return head;
    } else {
      cache.add(head);
    }
    head = head.next;
  }
  return null;
};

结果如下：

真正的难点在下面：可否使用 O1 的空间复杂度解决此题。

这个限制条件禁止了我们使用缓存，那么要怎样才能找到入口节点呢？

• 首先，限制了缓存，我们可以使用快慢节点的方式来判断环形链表
• 接下来的关键就是找到 fast 和 slow 的关系了

先来看一下图：

• 设 fast 和 slow 在 meet 节点相遇
• 设从 head 到 entry 的距离为 a
• 设从 entry 到 meet 的距离为 b
• 设从 meet 到 entry 的距离为 c

这里我们已知当 fast 和 slow 相遇时，fast 跑了两圈，也就是：

稍微计算一下就可以得到 的结论。

到这里就找到了 slow 和 fast 的关系，有什么用呢？

我们可以再设置一个 start 指针，当 fast 和 slow 在 meet 相遇时，让 start 以和 slow 相同的速度前行，因为 ，所以当 start 和 slow 相遇时，必然是在 entry 节点，届时返回该节点即可：

var detectCycle = function (head) {
  let slow = head;
  let fast = head;
  let start = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      while (slow && start) {
        if (slow === start) {
          return start;
        }
        slow = slow.next;
        start = start.next;
      }
    }
  }
  return null;
};

当然，嫌嵌套不好看的话可以稍微优化一下：

const findEntry = (start, slow) => {
  while (slow && start) {
    if (slow === start) return start;
    slow = slow.next;
    start = start.next;
  }
};

var detectCycle = function (head) {
  let slow = head;
  let fast = head;
  let start = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return findEntry(start, slow);
  }
  return null;
};

结果如下：