Tortoise and Hare Algorithm

Floyd's cycle-finding algorithm or Tortoise-Hare algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds.

To enhance efficiency, the Tortoise and Hare Algorithm is introduced as an optimization where the middle node can be found in just one traversal.

The Tortoise and Hare algorithm works because the fast-moving hare reaches the end of the list in exactly the same time it takes for the slow-moving tortoise to reach the middle. When the hare reaches the end, the tortoise is guaranteed to be at the middle of the list.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
 
class LinkedList {
  constructor() {
    this.head = null;
  }
 
  getMiddle = () => {
    if (!this.head || !this.head.next) return this.head;
 
    let slow = head;
    let fast = head;
 
    while (fast && fast.next) {
      slow = slow.next; // Move slow one step
      fast = fast.next.next; // Move fast two steps
    }
 
    return slow; // Slow is now at the middle node
  };
}
 
// Time complexity: O(n/2) = O(n)
// Space complexity: O(1)