Floyd's Cycle Detection Algorithm

Normal Way of Detecting a cycle

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head, visited = new Set()) {
  if (!head) return false
  if (visited.has(head)) return true
  visited.add(head)
  return hasCycle(head.next, visited)
};

Normal Way of Detecting the Node Where the cycle Begins

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head, visited = new Set()) {
  if (!head) return null
  if (visited.has(head)) return head
  visited.add(head)
  return detectCycle(head.next, visited)
};

Floyd's Cycle Detection Algorithm

Floyd's Cycle Detection Algorithm, also known as the Tortoise and Hare algorithm, is a classic technique used to detect cycles in a sequence or linked list. It is an efficient algorithm with a time complexity of O(n) and space complexity of O(1), making it suitable for detecting cycles in data structures where additional space is limited.

Overview

The algorithm uses two pointers (often called the tortoise and the hare) that traverse the sequence at different speeds:

• Tortoise: Moves one step at a time.
• Hare: Moves two steps at a time.

If there is a cycle in the sequence, the hare and the tortoise will eventually meet at some point within the cycle. If there is no cycle, the hare will reach the end of the sequence (e.g., null in a linked list).

Algorithm Steps

1. Initialization: Start both pointers at the beginning of the sequence.
2. Traversal:
   • Move the tortoise by one step.
   • Move the hare by two steps.
   • Continue until the hare either meets the tortoise (cycle detected) or reaches the end (no cycle).
3. Detection:
   • If the hare and tortoise meet, a cycle exists.
   • If the hare reaches the end, there is no cycle.

Example: Detecting a Cycle in a Linked List

JavaScript Implementation:

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

/**
 * Detect if a cycle exists in a linked list using Floyd's Cycle Detection Algorithm.
 * @param {ListNode} head - The head of the linked list.
 * @return {boolean} - True if a cycle is detected, false otherwise.
 */
const hasCycle = (head) => {
  if (!head || !head.next) return false;

  let tortoise = head;
  let hare = head;

  while (hare && hare.next) {
    tortoise = tortoise.next;        // Move tortoise one step
    hare = hare.next.next;           // Move hare two steps

    if (tortoise === hare) return true; // Cycle detected
  }

  return false; // No cycle
}

// Example usage:
const node3 = new ListNode(3);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
node3.next = node1; // Creates a cycle: 1 -> 2 -> 3 -> 1

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

Duplicate Element

Find the Duplicate Number

/**
 * @param {number[]} nums
 * @return {number}
 */
const findDuplicate = (nums) => {
  // Step 1: Finding the intersection point
  let tortoise = nums[0];
  let hare = nums[0];

  do {
    tortoise = nums[tortoise]; // Move tortoise by one step
    hare = nums[nums[hare]];    // Move hare by two steps
  } while (tortoise !== hare);

  // Step 2: Finding the entry point of the cycle
  tortoise = nums[0];
  while (tortoise !== hare) {
    tortoise = nums[tortoise];
    hare = nums[hare];
  }

  return tortoise; // This is the duplicate number
};
const nums = [1,3,4,2,2]
findDuplicate(nums) //2

Break a Cycle in Linkedlist

function breakCycle(head) {
  let s = head
  let f = head

  //Find Cycle
  while (f && f.next) {
    s = s.next
    f = f.next.next
    if (s === f) break
  }

  if (!f || !f.next) return

  //Start Node
  s = head
  while (f !== s) {
    s = s.next
    f = f.next
  }

  //Prev node

  while (f.next !== s) {
    f = f.next
  }

  f.next = null

  return head
}

Linkedlist Cycle length

function cycleLength(head) {
  let slow = head, fast = head;

  // Step 1: Detect Cycle
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) { // Cycle detected
      let count = 1;
      let current = slow.next;

      // Step 2: Count the number of nodes in the cycle
      while (current !== slow) {
        count++;
        current = current.next;
      }

      return count;
    }
  }

  return 0; // No cycle
}