Detect a Cycle in a Linked List Tutorial

What Is a Cycle in a Linked List?

A cycle in a linked list occurs when a node points back to an earlier node instead of eventually pointing to null. As a result, following the next references can cause traversal to continue indefinitely.

A normal singly linked list has a structure such as:

10 → 20 → 30 → 40 → null

A cyclic linked list may look like:

10 → 20 → 30 → 40
          ↑         ↓
          └─────────┘

Here, the node containing 40 points back to 20. The traversal therefore follows:

20 → 30 → 40 → 20 → 30 → 40 → ...

Why Cycle Detection Matters

A cycle can cause a normal linked list traversal to become an infinite loop. This can lead to an application continuously processing the same nodes instead of terminating.

Detecting cycles is useful when validating linked structures and is also an important interview problem because it tests traversal, references, and pointer techniques.

A Simple Approach Using a Set

One straightforward way to detect a cycle is to store every visited node in a Set. Before processing a node, check whether that exact node has already been visited.

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

  while (current !== null) {
    if (visited.has(current)) {
      return true;
    }

    visited.add(current);
    current = current.next;
  }

  return false;
}

This works because JavaScript objects are compared by reference. If the same node object is reached again, the set can identify it.

Complexity of the Set-Based Approach

The set-based approach can visit each node once, giving O(n) time in the worst case. However, it stores references to visited nodes, requiring O(n) additional space.

Aspect	Complexity
Time	O(n)
Extra Space	O(n)

Floyd's Cycle Detection Algorithm

Floyd's cycle detection algorithm, also called the tortoise and hare algorithm, detects a cycle using two pointers that move through the linked list at different speeds.

Slow pointer: moves one node at a time.
Fast pointer: moves two nodes at a time.

If there is no cycle, the fast pointer eventually reaches null. If a cycle exists, the fast pointer eventually catches up with the slow pointer inside the cycle.

How the Slow and Fast Pointers Work

Consider a list where the last node points back to the second node:

10 → 20 → 30 → 40
     ↑         ↓
     └─────────┘

The slow pointer moves one step:

slow = slow.next

The fast pointer moves two steps:

fast = fast.next.next

Once both pointers enter the cycle, the faster pointer eventually catches the slower one. They will therefore refer to the same node at some point.

Implementing Floyd's Algorithm

The standard implementation starts both pointers at the head. The loop continues while the fast pointer and its next node are available.

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;
}

The comparison uses reference equality. The algorithm is checking whether both pointers refer to the same node, not whether their stored data values are equal.

Why Two Pointers Meet Inside a Cycle

Once both pointers are inside the cycle, the fast pointer gains one node on the slow pointer during every iteration because it moves two steps while the slow pointer moves one.

Because the cycle contains a finite number of nodes, repeatedly gaining one position eventually causes the fast pointer to occupy the same node as the slow pointer.

Slow:  → 20 → 30 → 40 → 20 → 30 → ...
Fast:  → 30 → 20 → 40 → 30 → 20 → ...

Eventually:

slow === fast

This meeting is the evidence that a cycle exists.

Cycle Detection Without Modifying the List

Floyd's algorithm does not change any node references. It only moves two local references through the existing list.

This makes it an in-place cycle detection technique with constant additional space.

Complete Example With a Cycle

The following example creates a linked list and intentionally connects the last node back to an earlier node.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

const first = new Node(10);
const second = new Node(20);
const third = new Node(30);
const fourth = new Node(40);

first.next = second;
second.next = third;
third.next = fourth;

// Create a cycle.
fourth.next = second;

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;
}

console.log(hasCycle(first)); // true

Example Without a Cycle

If the final node points to null, the fast pointer eventually reaches the end of the list.

10 → 20 → 30 → 40 → null

In this case, the loop terminates without the two pointers meeting, so the function returns false.

Finding the Starting Node of a Cycle

Detecting whether a cycle exists is only one part of the problem. Floyd's algorithm can also be extended to find the node where the cycle begins.

First, move the slow and fast pointers until they meet. If they meet, reset one pointer to the head. Then move both pointers one step at a time. The node where they meet again is the beginning of the cycle.

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

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      slow = head;

      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }

      return slow;
    }
  }

  return null;
}

This returns the actual node where the cycle begins, or null when the linked list has no cycle.

Example of Finding the Cycle Start

Consider:

10 → 20 → 30 → 40
     ↑         ↓
     └─────────┘

The cycle begins at 20. Floyd's algorithm first detects a meeting somewhere inside the cycle. After resetting one pointer to the head and moving both pointers at the same speed, they meet at 20.

Measuring the Cycle Length

After Floyd's algorithm detects a meeting point, the cycle length can also be calculated. Keep one pointer at the meeting node and move another pointer around the cycle until it returns to the meeting point.

function getCycleLength(meetingNode) {
  let length = 1;
  let current = meetingNode.next;

  while (current !== meetingNode) {
    current = current.next;
    length++;
  }

  return length;
}

If the cycle contains three nodes, the function returns 3.

Floyd's Algorithm Complexity

Aspect	Complexity
Time	O(n)
Extra Space	O(1)

The algorithm uses only two pointer variables regardless of the number of nodes, so its additional space remains constant.

Floyd's Algorithm vs Set-Based Detection

Approach	Time	Extra Space	Main Idea
Set	O(n)	O(n)	Remember every visited node
Floyd's algorithm	O(n)	O(1)	Use slow and fast pointers

Both approaches can detect a cycle in linear time. The main difference is the additional memory used by the set-based solution.

Cycle vs Circular Linked List

A circular linked list intentionally contains a cycle as part of its structure. In a regular linked list, however, a cycle is usually considered an unexpected structural condition.

For example, a circular linked list is deliberately designed as:

10 → 20 → 30 → 10 → ...

A standard singly linked list is normally expected to terminate:

10 → 20 → 30 → null

Therefore, cycle detection is particularly useful when working with linked structures that are expected to terminate.

Common Cycle Detection Mistakes

Comparing node values instead of comparing node references.
Forgetting to check fast.next before accessing fast.next.next.
Using only one pointer and expecting it to detect a cycle by itself.
Returning false as soon as the slow pointer repeats a value.
Confusing duplicate data values with repeated node references.
Modifying the linked list unnecessarily while checking for a cycle.

Duplicate Values Are Not a Cycle

A linked list can contain duplicate values without containing a cycle. Cycle detection should therefore compare node references, not the values stored inside nodes.

10 → 20 → 10 → 30 → null

The value 10 appears twice, but these can be two different node objects. There is no cycle because the list eventually reaches null.

A Useful Mental Model

Think of the linked list as a path. In an acyclic list, the path eventually ends. In a cyclic list, the path loops back to a node that has already been visited.

No cycle:

A → B → C → D → null

Cycle:

A → B → C → D
    ↑       ↓
    └───────┘

The slow and fast pointers exploit this difference. The fast pointer cannot indefinitely stay ahead of the slow pointer once both are moving inside a finite cycle.

Linked List Cycle Detection in Interviews

Detecting a cycle is a common linked list interview problem. The basic question usually asks whether a linked list contains a cycle, but variations may ask for the starting node, cycle length, or additional information about the cyclic portion.

A good solution should clearly handle an empty list, a single-node list, an acyclic list, and a cycle that points back to any earlier node.

Key Takeaways

A cycle occurs when a node points back to an earlier node in the linked list.
A normal traversal can become an infinite loop when a cycle exists.
A Set can detect cycles in O(n) time using O(n) extra space.
Floyd's cycle detection algorithm uses slow and fast pointers.
Floyd's algorithm detects a cycle in O(n) time and O(1) extra space.
Node references should be compared instead of node data values.
Floyd's algorithm can also find the starting node of a cycle.
A circular linked list intentionally contains a cycle, while a cycle in a normal linked list may indicate an unexpected structure.

Topics

Detect a Cycle in a Linked List