Solving Linked List Cycle in JavaScript: Step-by-Step Guide

Solving Linked List Cycle in JavaScript: Step-by-Step Guide

The Linked List Cycle problem is one of the most classic algorithmic challenges you will encounter in technical interviews and real-world debugging scenarios. At its core, the problem asks a deceptively simple question: given the head of a singly linked list, determine whether the list contains a cycle — that is, whether any node's next pointer eventually points back to a previously visited node, creating an infinite loop.

In this tutorial, we will explore what a linked list cycle is, why detecting it matters, and how to solve it efficiently in JavaScript using multiple approaches. By the end, you will understand both the intuitive and optimal solutions, along with the trade-offs between them.

What Is a Linked List Cycle?

A singly linked list is a linear data structure where each node contains a value and a pointer (commonly called next) to the following node. The final node in a properly terminated list points to null, signaling the end. A cycle occurs when, instead of pointing to null, a node's next pointer references an earlier node in the list. This creates a closed loop, meaning traversal would never naturally terminate.

Consider the following representation of a linked list with a cycle:

1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |_________|

In this example, the node containing 5 points back to the node containing 3. If you begin traversing from the head, you will move through 1, 2, 3, 4, 5, 3, 4, 5, 3, ... indefinitely. Detecting this condition is essential because naive traversal algorithms would loop forever, consuming CPU and potentially crashing your application.

Why Detecting Cycles Matters

Cycles in linked lists are not merely academic curiosities. They appear in real systems whenever references are manipulated dynamically. Some scenarios where cycle detection is critical include:

• Memory management: Garbage collectors must identify reference cycles to reclaim memory properly.
• State machines: Graph-like structures built on linked references can accidentally form loops.
• Serialization: Attempting to serialize a cyclic structure without detection causes infinite recursion or stack overflows.
• Interviews: The problem tests your understanding of pointers, time and space complexity, and algorithmic creativity.

Failing to detect a cycle can lead to infinite loops, stack overflows, or subtle data corruption. Understanding how to identify and handle these cycles is therefore a foundational skill for any JavaScript developer working with dynamic data structures.

Defining the Node Structure

Before implementing any solution, we need a consistent representation of a linked list node. In JavaScript, we typically define it using a class:

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

Each node stores a value and a reference to the next node. To create a list with a cycle for testing, we manually wire the next pointers so that the tail points back to an earlier node:

function createCyclicList() {
  const head = new ListNode(1);
  const second = new ListNode(2);
  const third = new ListNode(3);
  const fourth = new ListNode(4);
  const fifth = new ListNode(5);

  head.next = second;
  second.next = third;
  third.next = fourth;
  fourth.next = fifth;
  fifth.next = third; // Creates the cycle: 5 -> 3

  return head;
}

With this setup, we can now build and test our detection algorithms.

Approach 1: Using a Set to Track Visited Nodes

The most intuitive solution involves traversing the list while storing every visited node in a Set. At each step, we check whether the current node has already been seen. If it has, a cycle exists. If we reach null, the list is properly terminated and contains no cycle.

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

  while (current !== null) {
    if (visited.has(current)) {
      return true; // Cycle detected
    }
    visited.add(current);
    current = current.next;
  }

  return false; // Reached the end, no cycle
}

This approach is straightforward and easy to reason about. However, it requires O(n) extra space because, in the worst case, we store every node in the set. For large lists, this can become a significant memory burden.

Approach 2: Floyd's Tortoise and Hare Algorithm

The optimal solution is Floyd's Cycle Detection Algorithm, commonly known as the tortoise and hare approach. It uses two pointers that traverse the list at different speeds: a slow pointer (the tortoise) moves one node at a time, while a fast pointer (the hare) moves two nodes at a time. If a cycle exists, the fast pointer will eventually lap the slow pointer and they will meet. If there is no cycle, the fast pointer will reach null first.

function hasCycleFloyd(head) {
  if (head === null || head.next === null) {
    return false;
  }

  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;          // Moves one step
    fast = fast.next.next;     // Moves two steps

    if (slow === fast) {
      return true; // Pointers met, cycle exists
    }
  }

  return false; // Fast pointer reached the end
}

The beauty of this algorithm lies in its efficiency. It runs in O(n) time and uses only O(1) extra space, since we only maintain two pointers regardless of the list size. The intuition is that within a cycle, the fast pointer gains one step on the slow pointer with each iteration, guaranteeing they will eventually collide.

Approach 3: Finding the Cycle's Starting Point

Sometimes merely detecting a cycle is not enough — you may need to identify where the cycle begins. Floyd's algorithm can be extended for this purpose. Once the slow and fast pointers meet, you reset one pointer to the head and then move both pointers one step at a time. The node where they meet again is the start of the cycle.

function detectCycleStart(head) {
  if (head === null || head.next === null) {
    return null;
  }

  let slow = head;
  let fast = head;
  let hasCycle = false;

  // Phase 1: Detect the cycle
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      hasCycle = true;
      break;
    }
  }

  if (!hasCycle) {
    return null;
  }

  // Phase 2: Find the start of the cycle
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }

  return slow; // This is the node where the cycle begins
}

The mathematical justification for this two-phase approach is elegant. If the distance from the head to the cycle's start is a, and the distance from the cycle's start to the meeting point is b, and the cycle length is c, then the slow pointer travels a + b while the fast pointer travels a + b + k*c (for some integer k). Since the fast pointer travels twice the distance, we get 2(a + b) = a + b + k*c, which simplifies to a = k*c - b. This means moving a steps from the head is equivalent to moving k*c - b steps from the meeting point, which lands exactly at the cycle's start.

Testing the Implementations

To verify that our solutions work correctly, we should test them against both cyclic and acyclic lists:

// Test with a cyclic list
const cyclicHead = createCyclicList();
console.log(hasCycleSet(cyclicHead));    // true
console.log(hasCycleFloyd(cyclicHead));  // true
console.log(detectCycleStart(cyclicHead).val); // 3

// Test with a non-cyclic list
const a = new ListNode(1, new ListNode(2, new ListNode(3)));
console.log(hasCycleSet(a));    // false
console.log(hasCycleFloyd(a));  // false
console.log(detectCycleStart(a)); // null

// Edge cases
console.log(hasCycleFloyd(null)); // false
console.log(hasCycleFloyd(new ListNode(1))); // false

Running these tests confirms that all three functions behave as expected across normal, edge, and boundary cases.

Best Practices

When implementing linked list cycle detection in production code or interviews, keep the following best practices in mind:

• Always handle edge cases: Check for null heads and single-node lists before entering the main loop to avoid runtime errors.
• Prefer the Floyd algorithm: It offers the best balance of time and space complexity, making it suitable for large datasets and memory-constrained environments.
• Use the Set approach for clarity: When readability matters more than memory — for example, in quick scripts or debugging tools — the Set-based solution is perfectly acceptable.
• Guard the loop condition carefully: Always check both fast !== null and fast.next !== null before advancing the fast pointer, otherwise you risk dereferencing null.
• Write tests for both scenarios: Ensure your solution is validated against cyclic lists, acyclic lists, single nodes, empty lists, and lists where the cycle starts at the head.
• Avoid mutating the input: Unless explicitly required, do not modify the list structure during detection, as this can introduce subtle bugs in calling code.

Conclusion

Detecting a cycle in a linked list is a fundamental problem that combines pointer manipulation, algorithmic thinking, and an understanding of time and space complexity. We explored three JavaScript solutions: the intuitive Set-based approach, the optimal Floyd's tortoise and hare algorithm, and an extension that locates the exact starting point of the cycle. Each method has its place depending on your constraints and goals, but Floyd's algorithm stands out for its elegance and efficiency, running in linear time with constant space. By mastering these techniques, you will be well-equipped to handle linked list problems in both technical interviews and real-world applications, while also building a deeper intuition for how references and memory behave in JavaScript.