Cycle Detection in Linked List

Detect cycle in a linked list

A linked list may have a cycle if one of the elements points to an element that’s already in the list.

Problem statement:

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.

How to model the linked list with FizzBee

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.

Implementation

We can start by generating a linked list that may contain a cycle.

Run in playground

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


POSSIBLE_NODES = list(range(1, 4))

action Init:
  # A dict from node to its successor.
  # Example: {1: 2, 2: 3, 3: None}
  successor = {}
  current = any POSSIBLE_NODES
  has_cycle = False
  while (current and not has_cycle):
    next = any list(POSSIBLE_NODES) + [None]
    successor[current] = next  
      
    has_cycle = next in successor
    current = next  

  nodes = successor.keys()
  start = any nodes

action NoOp:
  pass

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>

Floyd’s algorithm

The algorithm can be implemented using a single atomic function.

Let there be two pointers called slow and fast
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 the fast 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

Finding cycle by keeping track of visited nodes

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

Safety invariants

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

Full code

Run in playground

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


POSSIBLE_NODES = list(range(1, 4))

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

action Init:
  # A dict from node to its successor.
  # Example: {1: 2, 2: 3, 3: None}
  successor = {}
  current = any POSSIBLE_NODES
  has_cycle = False
  while (current and not has_cycle):
    next = any POSSIBLE_NODES + [None]
    successor[current] = next  
      
    has_cycle = next in successor
    current = next  

  nodes = successor.keys()
  start = any nodes
  print(successor)

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

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

action NoOp:
    pass

Compare with TLA+

This example was inspired this post by Lorin Hochstein which models Floyd’s algorithm in TLA+.

Remember, FizzBee is a multi-paradigm language, so you can use the style that suits you best.