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 = None

def has_cycle(head):
    slow = head
    fast = head
    while fast is not None and is not None:
        slow =
        fast =
        if slow == fast:
            return True
    return False

if __name__ == "__main__":

    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4) = node2 = node3 = node4 = node2  
    has_cycle_result = has_cycle(node1)
    if has_cycle_result:
        print("The linked list contains a cycle.")
        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

Python Program to Detect Cycle in a Linked List