写点什么

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

用户头像
Lee Chen
关注
发布于: 2020 年 07 月 17 日

阅读更多系列文章请访问我的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;

};

```



发布于: 2020 年 07 月 17 日阅读数: 53
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:141. 环形链表,JavaScript,快慢指针,详细注释