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")
You must be logged in to post a comment.