This Python program detects a cycle in a linked list using Floyd’s Cycle Detection Algorithm. In computer science, a linked list is a data structure used to store a sequence of elements.
A linked list is composed of nodes, where each node contains a value and a reference (or link) to the next node in the sequence. One common challenge in working with linked lists is detecting whether the list contains a cycle, i.e., if there is any sequence of nodes that loops back to a previous node. This program demonstrates how to detect a cycle in a linked list using Python.
Given a linked list, we need to determine whether the linked list contains a cycle or not.
Python Program to Detect Cycle in a Linked List
class ListNode: def __init__(self, value): self.value = value self.next = None def has_cycle(head): slow = head fast = head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next if slow == fast: return True return False if __name__ == "__main__": node1 = ListNode(1) node2 = ListNode(2) node3 = ListNode(3) node4 = ListNode(4) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node2 has_cycle_result = has_cycle(node1) if has_cycle_result: print("The linked list contains a cycle.") else: print("The linked list does not contain a cycle.")
How it works
- The program defines a
ListNodeclass to represent each node in the linked list.
has_cyclefunction takes the head node of the linked list as input and uses the Floyd’s Tortoise and Hare algorithm to detect cycles.
- In this algorithm, two pointers – slow and fast – traverse the linked list at different speeds.
- If there is a cycle, eventually the fast pointer will catch up to the slow pointer.