LeetCode #141 Linked List Cycle with JavaScript

Solutions to LeetCode's 141. Linked List Cycle with JavaScript.

Solution 2 also addresses the following follow-up.
Follow up: Can you solve it using O(1) (i.e. constant) memory?

Solution 1

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const hasCycle1 = (head) => {
  const list = [];
  while (head) {
    if (list.includes(head.val)) return true;
    list.push(head.val);
    head = head.next;
  }
  return false;
};

• Time complexity: O(n)
• Space complexity: O(n)

Space complexity is O(n), so change to address follow-up.

Solution 2

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

• Time complexity: O(n)
• Space complexity: O(1)

fast is 2 steps at a time, slow is 1 step at a time, and the list is put in a while loop to execute the search.

Comments

[Partha Roy]

The first solution works only if the list has no duplicate values.