Linked List CycleEasy

Given the head of a linked list, determine if it contains a cycle.

Examples

A list where the last node's `next` points back to an earlier node → true

Approach

Remembering every visited node in a Set catches cycles but costs O(n) space. Floyd's Cycle Detection (tortoise and hare) does it in O(1) space: run two pointers through the list at different speeds, one step at a time and two steps at a time. If there's no cycle, the fast pointer simply reaches the end. If there is a cycle, the fast pointer eventually laps the slow one from behind and they land on the same node — like two runners on a circular track.

Complexity — best & worst case

Set approach — space O(n)

Floyd's (optimal) — time O(n) worst case (fast pointer must lap the whole cycle), O(1) best case (the second node already points back to the first)

Floyd's (optimal) — space O(1)

Code

// Given the head of a linked list, determine if it has a cycle
// (some node's `next` eventually points back to a previous node).

class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

// --- Brute force: remember every node visited in a Set, O(n) space ---
function hasCycleSet(head) {
  const seen = new Set();
  let current = head;
  while (current) {
    if (seen.has(current)) return true;
    seen.add(current);
    current = current.next;
  }
  return false;
}

// --- Optimal: Floyd's Cycle Detection ("tortoise and hare"), O(1) space ---
// Two pointers move through the list at different speeds. If there's
// no cycle, the fast one hits the end. If there IS a cycle, the fast
// pointer eventually laps the slow one and they meet — same idea as
// two runners on a circular track at different speeds.
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;
}

// --- Example Usage ---
const a = new ListNode(1);
const b = new ListNode(2);
const c = new ListNode(3);
a.next = b;
b.next = c;
c.next = a; // creates a cycle back to `a`

console.log("hasCycle (with cycle):", hasCycle(a));   // true
console.log("hasCycleSet (with cycle):", hasCycleSet(a)); // true

const clean = new ListNode(1, new ListNode(2, new ListNode(3)));
console.log("hasCycle (no cycle):", hasCycle(clean)); // false