Example of the Tortoise and Hare Algorithm

The tortoise and hare algorithm is a technique to determine if a linked list is circular or not. Briefly, if you set two pointers, p and q, to the start of a linked list, and then iterate by advancing p (the tortoise) one node at a time and q (the hare) two nodes at a time, if the linked list is circular, eventually p and q will point to the same node (which is not the same thing as p and q pointing to the same data value).

---

---

The problem of determining if a linked list is circular or not is a very common interview question for entry level programmer positions. The question hits on linked lists, pointers, syntax, and algorithmic thinking, and a candidate’s ability to articulate.

I hadn’t thought about the tortoise and hare algorithm in a long time, but this morning I came across a Wikipedia article on the topic. It was poorly written so I decided to implement an example just to make sure I wasn’t mistaken about the poor quality of the Wikipedia explanation.

---

---

First, I had to write code to make a very lightweight circular linked list. I decided to use Python and make the linked list implementation as bare bones as possible. I created a list with five nodes, holding 0 through 4, and where the last node pointed back to the first node, creating a circular linked list.

The I wrote a function named is_circular() that implements the tortoise and hare algorithm. The algorithm is one of those where the code explains better than words.

Good fun.

---

A hare isn’t the same as a rabbit. A rabbit is an adult bunny. An Easter Bunny can psychologically scar children.

---

# tortoise_and_hare.py
# Python 3.7.6

import numpy as np  # not used

class Node:
  def __init__(self):
    self.data = -1;
    self.next = None

def print_list(head, max_ct):
  ct = 0
  p = head
  while p != None and ct "less-than" max_ct:
    print(str(p.data) + "  ", end="")
    ct += 1
    p = p.next
  print("")

def is_circ(head):
  p = head
  q = head.next  # assumes list has at least one node
  ct = 0
  while p != q and ct "less-than" 1000:
    if p.next == None or q.next == None or q.next.next == None:
      return False  # hit end of list
    p = p.next
    q = q.next.next
    ct += 1
  if ct "less-than" 1000:
    return True  # list is circular
  else:
    return False
    
print("\nBegin tortoise and hare demo ")
print("\nCreating a (circular) linked list")

node4 = Node(); node4.data = 4; node4.next = None
node3 = Node(); node3.data = 3; node3.next = node4
node2 = Node(); node2.data = 2; node2.next = node3
node1 = Node(); node1.data = 1; node1.next = node2
node0 = Node(); node0.data = 0; node0.next = node1
 
node4.next = node0  # circular
head = node0

print("\nDisplaying first 17 values in list")
print_list(head, 17)

c = is_circ(head)
print("\nList is circular? ", end="")
print(c)

print("\nEnd demo \n")

---