Overview

Given the head of a linked list, determine if the list has a cycle in it. A cycle exists if some node can be reached again by continuously following the next pointer.

Return true if a cycle exists, false otherwise. Use O(1) extra space.

Constraints

• The list has 0 to 10,000 nodes.
• Node values are integers.
• Use constant extra space (no hash set).

Examples

// 3 -> 2 -> 0 -> -4
//      ^-----------+  (cycle back to node 2)
hasCycle(head); // => true

// 1 -> 2 -> null
hasCycle(head); // => false

// null (empty list)
hasCycle(null); // => false

Solution

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }

  return false;
}

Resources

• Linked List Cycle — LeetCode
• Floyd's Cycle Detection — Wikipedia