Tortoise and Hare Pointers

So… this algorithm seems (at face value) rather pointless outside the context of a coding interview question. However, if you give it “a chance”, you’ll see that the Tortoise and Hare Pointer/Fast and Slow Pointer Pattern reveals the basic mechanic of identifying an Infinite Loop. While the example below does not account for what you ought to do if an Infinite Loop is discovered, the pattern (in the abstract) might give you a sense of how to identify it.

I would suspect some version of this pattern could be useful for Data Scientists working with gigantic Data Sets, or programmers working with graphics that need to render. Likewise, for any piece of hardware that runs a microcomputer.

It almost goes without saying that any system with a closed interface ought have the power to deal with an infinite loop, especially if it cannot be shut down. For example: an autonomous delivery drone, or self driving car may rely on some foundational “fast and slow” pointer pattern to prevent its systems from falling into an infinite loop.

Here is a coding example:

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

function infinite_loop(head) {
  let tortoise = head
  let hare = head;
  while (hare !== null && hare.next !== null) {
    hare = hare.next.next;
    tortoise = tortoise.next;
    if (tortoise === hare) {
      return true; 
    }
  }
  return false;
}


const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
console.log(`Infinite Loop: ${infinite_loop(head)}`);

head.next.next.next.next = head.next;
console.log(`Infinite Loop: ${infinite_loop(head)}`);

Cast of Characters:
-Wart Nose
-Class Room
-Construction Workers
-Two Face
-Wile E Coyote
-Tortoise & Hare … specific to this algorithm

Glossary of Code Personified

Return to the Pattern Directory