5.环形链表

经典题目，判断链表是否有环，这个题目有多种解法，我们先看最简单的解法，快慢指针。

解题思路

设置两个指针，一个快指针，一个慢指针，快指针每次走两步，慢指针每次走一步，如果链表有环，那么快指针一定会追上慢指针，如果没有环，那么快指针会先到达链表末尾。

如何证明快指针一定会追上慢指针呢？我们可以这样理解，假设链表有环，那么快指针每次走两步，慢指针每次走一步，那么快指针每次比慢指针多走一步，所以快指针一定会追上慢指针。就好比两个人在操场跑步，一个人每次走两步，一个人每次走一步，那么两个人一定会相遇。因为两个人的步数差是 1，相当于慢指针不动，快指针每次走一步，所以快指针一定会追上慢指针。

// 快慢指针

function hasCycle(head) {
    // 快慢指针初始化指向 head
    var slow = head, fast = head;
    // 如果没有环，快指针一定是先到达链表末尾，到达末尾跳出循环，证明没有环
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

比较难的还是 Leetcode 的 142 题环形链表

如果链表有环，那么如何找到这个环的入口呢？我们可以这样理解，假设链表有环，那么快指针一定会追上慢指针，当快指针追上慢指针的时候，我们可以让快指针从头开始走，慢指针继续走，当快指针和慢指针再次相遇的时候，就是环的入口。这是数学证明，可以通过画图来理解。

此处为 Leetcode 题解的数学证明步骤

// 找到环的入口
var detectCycle = function (head) {
  // 第一轮快慢指针，用于判断是否有环
  let fast = head;
  let slow = head;
  // 第一轮相遇的节点
  let meet;
  // 条件依然为快指针不能为 null，快指针的下一个节点也不能为 null
  while (fast && fast.next) {
    // 慢指针走一步，快指针走两步
    slow = slow.next;
    fast = fast.next.next;
    // 如果相遇，证明有环
    if (fast === slow) {
      // 记录相遇的节点
      meet = slow;
      break;
    }
  }
  // 重置指针
  let p1 = head;
  let p2 = meet;
  if (meet) {
    while (p1) {
      // 相遇的地方开始走，头节点开始走，相遇的地方就是环的入口
      if (p1 === p2) {
        return p1;
      }
      p1 = p1.next;
      p2 = p2.next;
    }
  } else {
    return null;
  }
};

5.环形链表 ​

解题思路 ​

5.环形链表

解题思路