Python: Detect and Remove Loop in Linked List

📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (176K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

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.