Lecture 200:- Check for LOOP in Linked List

Detecting a loop in a linked list can be done using the Floyd's cycle detection algorithm (also known as the "tortoise and the hare" algorithm). It is an efficient approach that uses two pointers to traverse the linked list at different speeds. If there is a loop, the two pointers will eventually meet at some point.

Here's the Python code to check for a loop in a linked list using the Floyd's cycle detection algorithm:

pythonCopy code

class Node:    def __init__(self, data):        self.data = data        self.next = None class LinkedList:    def __init__(self):        self.head = None    def append(self, data):        new_node = Node(data)        if not self.head:            self.head = new_node        else:            current_node = self.head            while current_node.next:                current_node = current_node.next            current_node.next = new_node    def display(self):        current_node = self.head        while current_node:            print(current_node.data, end=" -> ")            current_node = current_node.next        print("None")    def has_loop(self):        if not self.head or not self.head.next:            return False        slow_ptr = self.head        fast_ptr = self.head.next        while fast_ptr and fast_ptr.next:            if slow_ptr == fast_ptr:                return True            slow_ptr = slow_ptr.next            fast_ptr = fast_ptr.next.next        return False # Example usage: linked_list = LinkedList() linked_list.append(1) linked_list.append(2) linked_list.append(3) linked_list.append(4) # Create a loop for testing (4 -> 2) linked_list.head.next.next.next.next = linked_list.head.next if linked_list.has_loop():    print("The linked list contains a loop.") else:    print("The linked list does not contain a loop.")

In this implementation, the has_loop function checks for a loop in the linked list. It uses two pointers (slow_ptr and fast_ptr) that traverse the list at different speeds. If there is a loop, the fast pointer will eventually catch up to the slow pointer, indicating the presence of a loop. If there is no loop, the fast pointer will reach the end of the list.

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. The algorithm efficiently detects loops without using any extra space.

In the example usage, we intentionally create a loop in the linked list by making the last node (4) point back to the second node (2). The has_loop function correctly identifies the loop in the linked list.