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