LeetCode 题解：141. 环形链表，JavaScript，快慢指针，详细注释

阅读更多系列文章请访问我的GitHub 博客



原题链接：https://leetcode-cn.com/problems/linked-list-cycle/



解题思路：

1. 两人同时出发，慢的人一次跑一步，快的人一次跑两步。

2. 如果存在环，那两人必然相遇。如果不存在，那快的人必然会先无路可走。



```javascript []

/**

 * @param {ListNode} head

 * @return {boolean}

 */

var hasCycle = function (head) {

  // 由于是双指针，必须保证head和head.next都存在

  if (!head || !head.next) {

    return false;

  }

  // 创建快慢指针

  let slow = head;

  let fast = head.next;

  // 链表有环，快慢指针必然相遇，表现为两个指针相等

  // 如果快慢指针未相遇，则继续前进

  while (slow !== fast) {

    // 如果快指针指向的节点为空，则代表不会出现环

    // 慢指针跑的慢，可以不用判断

    if (!fast.next || !fast.next.next) {

      return false;

    }

    // 慢指针前进一个节点，快指针前进两个节点

    slow = slow.next;

    fast = fast.next.next;

  }

  return true;

};

```

```javascript []

/**

 * @param {ListNode} head

 * @return {boolean}

 */

var hasCycle = function (head) {

  if (!head || !head.next) {

    return false;

  }

  let slow = head;

  let fast = head;

  while (fast && fast.next) {

    slow = slow.next;

    fast = fast.next.next;

    if (slow === fast) {

      return true;

    }

  }

  return false;

};

```

优化后代码：

```javascript []

/**

 * @param {ListNode} head

 * @return {boolean}

 */

var hasCycle = function (head) {

  let slow = head; // 慢指针

  let fast = head; // 快指针

  // 如果快指针还可以移动，则继续遍历链表。

  // 如果无法移动，表示没有环

  while (fast && fast.next && fast.next.next) {

    // 分别移动快慢指针

    slow = slow.next;

    fast = fast.next.next;

    // 快慢指针相同时，即为发生碰撞，表示有换

    if (slow === fast) {

      return true;

    }

  }

  return false;

};

```