leetcode-141 环形链表

环形链表

解法一

空间复杂度O(n)

遍历链表，以此添加进入集合，重复出现即出现了环

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let cur = head;
  const set = new WeakSet();
  while (cur) {
    if (set.has(cur)) {
        // 存在环
      return true;
    } else {
      set.add(cur);
    }
    cur = cur.next;
  }
  return false;
};

解法二

空间复杂度O(1)

快慢指针

如果存在环形链表，快指针会赶超慢指针，并在一个位置相遇

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  if (!head) return false;
  let slow = head,
    fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
};

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。