141. 环形链表 | LeetCode算法题解

题目描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例：

略。

进阶： 你能用 O(1)（即，常量）内存解决此问题吗？

来源：LeetCode

思路

标记法，遍历链表，对于访问到的节点进行标记，若再次访问到已标记节点，说明有环。

此方法所需内存随链表长度增加而增加，即 O(n)。不符合要求。

快慢指针法，链表问题中的经典办法。慢指针一次一步，快指针一次两步，若链表有环，它们一定会相遇。

此方法，只需额外两个变量，空间复杂度为 O(1)。

解法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const hasCycle = function(head) {
  if (!head) return false;

  let slow = head;
  let fast = head.next;

  while (fast) {
    if (slow === fast) return true;

    slow = slow.next;
    fast = fast.next ? fast.next.next : null;
  }

  return false;
};