Python Program to Detect Cycle in a Linked List

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.

Problem Statement

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

1. The program defines a ListNode class to represent each node in the linked list.
2. The has_cycle function takes the head node of the linked list as input and uses the Floyd’s Tortoise and Hare algorithm to detect cycles.
3. In this algorithm, two pointers – slow and fast – traverse the linked list at different speeds.
4. If there is a cycle, eventually the fast pointer will catch up to the slow pointer.

Input / Output