## 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

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

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 ")

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