The Floyd’s Cycle Detection Algorithm, also known as the Tortoise and Hare algorithm, is a classic and elegant approach to detect cycles in linked lists or sequences.

It uses two pointers moving at different speeds — one slow (the tortoise) and one fast (the hare). If there’s a cycle, they will eventually meet.

The Idea

The main idea is simple:

1. Initialize two pointers — both start at the head of the list.
   • slow moves one step at a time.
   • fast moves two steps at a time.
2. If the list has a cycle, eventually the fast pointer will “lap” the slow pointer and they’ll meet.
3. If the fast pointer reaches the end (null), then there’s no cycle.

Optionally, once a cycle is detected, you can find the starting node of the cycle using a clever trick (explained below).

Implementation in JavaScript

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

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; // Cycle detected
    }
  }

  return false; // No cycle
}

// Example usage:

// Creating a linked list with a cycle
const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // Creates a cycle

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

// Creating a list without a cycle
const a = new ListNode(1);
const b = new ListNode(2);
a.next = b;

console.log(hasCycle(a)); // false`}

Finding the Start of the Cycle (Optional)

If you need to find the node where the cycle begins, you can extend the algorithm:

1. When slow and fast meet, keep one pointer at the meeting point.
2. Move the other pointer back to the head.
3. Move both pointers one step at a time — the point where they meet again is the start of the cycle.

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

  // Step 1: Detect if a cycle exists
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

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

  return null; // No cycle
}

Example Walkthrough

Let’s say we have this linked list:

1 → 2 → 3 → 4 → 5 ↑ ↓ ← ← ← ← ←

• The slow pointer moves one step at a time.
• The fast pointer moves two steps at a time.
• When there’s a loop, they’ll meet somewhere inside it.
• Reset slow to head and move both one step at a time to find the start.

Time and Space Complexity

Common Use Cases

• Detecting cycles in linked lists
• Identifying loops in graphs or sequences
• Detecting repetition in pseudo-random generators
• Finding cycle beginnings in Floyd’s Tortoise and Hare type problems