Python Program to Detect a Loop in a Linked List

In this tutorial, we will write a Python program to detect whether a singly linked list contains a loop. A loop in a linked list occurs when a node’s next pointer points to one of the previous nodes, forming a cycle.

Program Structure and Explanation

The program utilizes Floyd’s Cycle-Finding Algorithm, also known as the “Tortoise and Hare” algorithm. This algorithm uses two pointers that traverse the linked list at different speeds. The idea is simple:

• The slow pointer moves one step at a time.
• The fast pointer moves two steps at a time.
• If the linked list has a loop, the fast pointer will eventually meet the slow pointer within the loop.
• If the linked list does not have a loop, the fast pointer will reach the end (i.e., `None`).

Python Program

class Node:
    """
    A class representing a single node in a linked list.
    
    Attributes:
        data: The data stored in the node.
        next: A reference to the next node in the linked list.
    """
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    """
    A class for creating a singly linked list and detecting a loop within it.
    
    Methods:
        append(data): Adds a new node with the specified data to the end of the list.
        detect_loop(): Returns True if there is a loop in the linked list, otherwise False.
    """
    def __init__(self):
        self.head = None

    def append(self, data):
        """
        Adds a new node with the specified data to the end of the list.
        
        Parameters:
            data: The data to be added to the new node.
        """
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def detect_loop(self):
        """
        Detects whether the linked list contains a loop.
        
        Returns:
            bool: True if a loop is found, False otherwise.
        """
        slow_ptr = self.head
        fast_ptr = self.head
        while slow_ptr and fast_ptr and fast_ptr.next:
            slow_ptr = slow_ptr.next          # Move slow pointer by one step
            fast_ptr = fast_ptr.next.next     # Move fast pointer by two steps
            if slow_ptr == fast_ptr:          # Check if the two pointers meet
                return True
        return False

Documentation

The program consists of two main classes:

1. Node Class

This class represents an individual node in a linked list. Each node contains:

• data: The data stored in the node.
• next: A reference to the next node in the list (or None if it is the last node).

2. LinkedList Class

This class represents the linked list itself and contains methods to manipulate and examine the list:

• append(data): Adds a new node with the specified data to the end of the linked list.
• detect_loop(): Implements Floyd’s Cycle-Finding Algorithm to detect if there is a loop in the list.

Example Usage

Here is an example of how to use the program to detect a loop in a linked list:

# Create a new linked list
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.append(4)
llist.append(5)

# Create a loop for testing: Connect the last node to the second node
llist.head.next.next.next.next.next = llist.head.next

# Detect loop
if llist.detect_loop():
    print("Loop detected!")
else:
    print("No loop detected.")

In this example, a loop is intentionally created by connecting the last node to the second node. The detect_loop() method will return True and print “Loop detected!”