Cycle Detection in Linked List
A linked list may have a cycle if one of the elements points to an element that’s already in the list.
 Given a linked list that may contain a cycle
 The algorithm should detect the cycle if it exists
Here’ a few examples of linked lists that contain cycles:
A <> A
A > B > A
A > B > B
A > B > C > A
A > B > C > B
and a few examples of linked lists that don’t contain cycles:
A
A > B
A > B > C
A > B means that node A points to node B.
In this post, we will model two algorithms:
 Floyd’s tortoise and hare algorithm for cycle detection
 An algorithm that keeps track of the visited nodes to find cycles.
The linked list model won’t use pointers. It’ll be a map called successor
where nodes are keys and the value associated to the key is the node’s successor in the list.
Given a list A > B > C
, successor
would look like this:
successor = {'A': 'B', 'B': 'C', 'C': None}
C has None as its successor because it is the last element in the list.
We can start by generating a linked list that may contain a cycle.


We set has_cycle
to True
when a list that contains a cycle is generated.
If we add print(successor)
at the end of Init
we’ll see that every possible list with and without cycles is being generated:
{1: None}
{2: None}
{3: None}
{1: 1}
{2: 2}
{3: 3}
{1: 2, 2: None}
{1: 2, 2: None}
{1: 3, 3: None}
{1: 3, 3: None}
{2: 1, 1: None}
{2: 1, 1: None}
{2: 3, 3: None}
{2: 3, 3: None}
{3: 1, 1: None}
{3: 1, 1: None}
{3: 2, 2: None}
{3: 2, 2: None}
{1: 2, 2: 1}
{1: 2, 2: 1}
{1: 2, 2: 2}
{1: 2, 2: 2}
{1: 3, 3: 1}
{1: 3, 3: 1}
{1: 3, 3: 3}
{1: 3, 3: 3}
{2: 1, 1: 1}
<rest of output omitted for brevity>
The algorithm can be implemented using a single atomic function.
 Let there be two pointers called
slow
andfast
 Choose any node in the linked list
 Both pointers point to the chosen node at first
 In each step of the algorithm, the
slow
pointer advances to the next node and thefast
pointer advances to the next next node.  At any point in time, if both pointers point to the same node, a cycle has been found. If any of the pointers reached the end of the list, there’s no cycle.
atomic func tortoise_and_hare():
tortoise = start
hare = start
while True:
# If the slow pointer has not reached the end of the list. Advance it by 1.
if tortoise != None:
tortoise = successor.get(tortoise)
# Advance the fast pointer by 2.
for _ in range(0, 2):
if hare != None:
hare = successor.get(hare)
if tortoise == None or hare == None:
return False
if tortoise == hare:
return True
We can also use an algorithm that keeps track of visited nodes to detect cycles and compare the result with the algorithm we are modeling.
 Initialize an empty set before executing the algorithm
 Choose any node in the linked list to be the current node
 If the node is in the set, a cycle has been found
 Add the chosen node to the set
 The current node becomes the successor of the current node
 Repeat the process starting from the set membership test until a cycle has been found or the end of the list is reached
atomic func find_cycle_by_keeping_visited_set():
current = start
visited = set()
while current != None:
if current in visited:
return True
visited.add(current)
current = successor.get(current)
return False
Since the both algorithms return True
or False
, the assertion for each algorithm can just check that the algorithm returns the expected result.
always assertion TortoiseAndHareFindsCycle:
found = tortoise_and_hare()
return has_cycle == found
always assertion VisitedSetFindsCycle:
found = find_cycle_by_keeping_visited_set()
return has_cycle == found


This example was inspired this post by Lorin Hochstein which models Floyd’s algorithm in TLA+.
Remember, FizzBee is a multiparadigm language, so you can use the style that suits you best.