[Floyd’s Algorithm] How to Detect a Cycle in a Linked List in Python?

In this tutorial you will learn how to implement a simple Python program to detect if a linked list consists of a cycle or not. If you need a brief refresher on linked lists, do check out this blog post

Definition of a Cycle in a Linked List

A linked list can consist of a cycle if a tail node of the linked list points to another node in the list. Let us see a small example to understand the concept of cycle in a linked list.

Definition of a Cycle in a Linked List
Fig 1: Cycle in a linked list

In the above figure, you can see that the tail node of the linked list, instead of pointing to NULL, points to another node — the second node in the list. If such a scenario arises, we say there is a cycle or a loop in a list.

Initialization and Setup

We will first begin by initializing the nodes and constructing the linked list.

from linked_list import Node, LinkedList
 
node1 =  Node(5)
node2 =  Node(6)
node3 =  Node(7)
node4 =  Node(8)
node5 =  Node(9)
 
 
ll = LinkedList()
 
ll.insert_back(node1)
ll.insert_back(node2)
ll.insert_back(node3)
ll.insert_back(node4)
ll.insert_back(node5)

Now, we will connect the fifth node to the 3rd node forming a cycle.

node5.next = node3

Approach 1: Naive Approach

We will now look at a simple approach to implement the logic to find out if the list consists of a cycle or not. One approach would be to store the address of the node in a dictionary as we traverse through the list and as soon as we come across a node whose address was already in the dictionary, we can say that there was a cycle in the list. Let us see how we can implement this in Python

 
addresses = {}
temp_node = node1
while (temp_node):
   address = id(temp_node)
   print(address)
   if address not in addresses:
       addresses[address] = 1
   else:
       print('cycle in a linked list')
       print(temp_node.data)
       break
   temp_node = temp_node.next

The disadvantage of the previous approach is that it takes 0(n) space complexity. Can we solve this problem in O(1) space complexity?

Approach 2: Floyd’s Cycle Detection Algorithm

We can solve this problem by initializing two pointers, a slow pointer, and a fast pointer. On every iteration, we increment the slow pointer by 1 and the fast pointer by 2. We then check if the slow pointer is equal to the fast pointer i.e. do both the pointers point to the same node. If that is the case, we can say that there is a cycle or a loop in a linked list. Once we find the cycle we can break out of the while loop

Demonstration

Let us imagine we have a list with 5 nodes as illustrated in the figure below. As you can see the tail node i.e. the node with a value of 9 is pointing to the node with the value 7 or the 3rd node in the list, thereby forming a loop or a cycle.

Iteration 1:  

In the first iteration, the slow pointer is incremented by 1 and the fast pointer by 2. As you can see in the figure below, the slow pointer is now pointing to the node with the value 6 and the fast pointer is pointing to the node with the value 7.

Iteration 2:

In the second iteration  the slow pointer points to the node with the value 7 and the fast pointer points to the node with the value 9 or the last node.

Iteration 3:

In the third iteration we observe that both the slow and fast pointers are pointing to the same  node i.e. the node with the value 8. In this case, we can conclude that there is a cycle in a list.

Let us know see how we can implement the adobe logic in Python. 

We first initialize the slow pointer and the fast pointer pointing to the head node or the first node. We then run a while loop, and we run the loop as long as the slow pointer is valid, the fast pointer is valid and the next value of the fast pointer is valid. We then keep incrementing the slow and fast pointers by 1 and 2 respectively and if both the pointers have the same address value, we break out of the loop and print that there was a cycle in a linked list. You can find the entire logic below.

slow_ptr = node1
fast_ptr = node1
 
while (slow_ptr and fast_ptr and fast_ptr.next):
   slow_ptr = slow_ptr.next
   fast_ptr = fast_ptr.next.next
   if slow_ptr == fast_ptr:
       print('loop in a linked list', slow_ptr.data)
       break
   else:
       print(slow_ptr.data, fast_ptr.data)

This algorithm is also called the Floyd’s cycle detection algorithm.

Conclusion

In this tutorial, we saw how we can detect a cycle in a loop using the Floyd’s cycle detection algorithm. This algorithm can detect a loop in O(1) space complexity and O(n) time complexity.