Linked List Cycle

Difficulty: Easy

You're given the head of a linked list. Somewhere in the list, a later node's pointer might loop back around to an earlier node instead of eventually reaching null — creating a cycle. Determine whether the list has a cycle anywhere in it.

You just need a yes/no answer; you don't need to say where the cycle starts or how long it is.

Examples

Input: head = [3, 2, 0, -4], the last node connects back to the node with value 2
Output: true

Input: head = [1, 2], the last node connects back to the first node
Output: true

Input: head = [1]
Output: false

A single node whose pointer is null has nowhere to loop back to.

Constraints

The number of nodes is between 0 and 10^4.
-10^5 <= Node.val <= 10^5

Approach

The straightforward approach is to remember every node you've visited in a set. If you ever land on a node that's already in the set, you've looped back around, so there's a cycle. If you instead run off the end of the list (reach null), there wasn't one. This works, but it spends extra memory tracking every node.

A cleverer approach uses two pointers moving at different speeds — a slow one that moves one node at a time, and a fast one that moves two nodes at a time. If there's no cycle, the fast pointer simply reaches the end first. If there is a cycle, the fast pointer eventually enters the loop and, lap by lap, closes the gap on the slow pointer until they land on the same node. This needs no extra memory at all.

Solutions

Brute Force — Track Visited Nodes

Walk the list one node at a time, remembering every node reference you've seen in a set. If the current node is already in the set, you've come back around to it, so there's a cycle. If you reach null before that happens, there's no cycle.

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

function hasCycle(head) {
  const visited = new Set();
  let node = head;

  while (node !== null) {
    if (visited.has(node)) return true;
    visited.add(node);
    node = node.next;
  }

  return false;
}

Time: O(n) · Space: O(n)

Optimal — Floyd's Tortoise and Hare

Use two pointers starting at the head: a slow one that advances one node per step, and a fast one that advances two nodes per step. If the fast pointer (or its next node) ever hits null, the list ends cleanly and there's no cycle. If instead the two pointers ever land on the exact same node, the fast one has lapped the slow one inside a loop, which can only happen if a cycle exists.

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

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

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

  return false;
}

Time: O(n) · Space: O(1)