DEV Community

Masaki Fukunishi
Masaki Fukunishi

Posted on

LeetCode #141 Linked List Cycle with JavaScript

#javascript #algorithms #leetcode

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; };
Enter fullscreen mode Exit fullscreen mode
  • 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; };
Enter fullscreen mode Exit fullscreen mode
  • 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.

Top comments (1)

Collapse
 
partharoylive profile image
Partha Roy •

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