Python: Detect and Remove Loop in Linked List

1. Introduction

Linked lists are among the fundamental data structures used in computer science. However, due to some programming errors or other factors, linked lists may sometimes contain loops, which can lead to various problems. In this post, we will implement and understand an algorithm to detect and remove a loop from a linked list.

2. Program Overview

1. Define the Node and LinkedList classes.

2. Implement the method to add nodes to the linked list.

3. Implement Floyd’s cycle-finding algorithm (also known as the "Tortoise and the Hare" algorithm) to detect the loop.

4. Once the loop is detected, remove the loop.

5. Demonstrate the program using a sample linked list.

3. Code Program

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        """Add a node to the end of the linked list."""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def detect_and_remove_loop(self):
        """Detect and remove loop from the linked list."""
        if not self.head:
            return

        # Initialize slow and fast pointers
        slow = self.head
        fast = self.head

        # Move slow by one and fast by two steps
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            # If they meet, then loop is detected
            if slow == fast:
                self.remove_loop(slow)
                return True  # Loop found
        return False  # No loop

    def remove_loop(self, loop_node):
        """Remove loop in the linked list using the loop node."""
        ptr1 = self.head
        ptr2 = loop_node

        # Find the starting point of the loop
        while True:
            ptr2 = loop_node
            while ptr2.next != ptr1 and ptr2.next != loop_node:
                ptr2 = ptr2.next
            if ptr2.next == ptr1:
                break
            ptr1 = ptr1.next

        # Remove the loop by setting the next of loop node to None
        ptr2.next = None

# Sample linked list with loop
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)
ll.append(5)
# Introducing loop: last node points back to the third node
ll.head.next.next.next.next.next = ll.head.next.next
loop_found = ll.detect_and_remove_loop()
print("Loop Detected:", loop_found)
if loop_found:
    print("Loop Removed!")

Output:

Loop Detected: True
Loop Removed!

4. Step By Step Explanation

1. We begin by defining the basic structures of Node and LinkedList.

2. We have an append method to add nodes to the end of our linked list.

3. The main functionality lies in detect_and_remove_loop. We use Floyd's cycle-finding algorithm to detect the loop. It uses two pointers moving through the sequence at different speeds.

4. Once a loop is detected (i.e., the slow pointer meets the fast pointer), we use the remove_loop method to identify the loop's starting point and remove the loop by setting the appropriate node's next pointer to None.

5. Our sample linked list demonstrates a loop, and we successfully detect and remove it.