Introduction

A linked list is a fundamental data structure in computer science, widely used to implement dynamic data structures. Linked lists offer many advantages but can sometimes contain loops, leading to unexpected behavior or infinite loops in some algorithms. In this article, we will disccuss  two method one is hashing and second one is Floyd's cycle-finding algorithm, to detect loops in linked lists correctly.

A linked list is a linear data structure consisting of a series of elements called nodes. Each node consists of two parts: data and a reference (pointer) to the next node. The reference to the last node returns null, it will indicating the list's end. While Each node points to the next node in a singly linked list, forming a unidirectional sequence.

Find Loop in a Linked List Using Hashing

1. First initialize an empty  HashMap which will stores the addresses of the visited nodes.

2. Now Traverse through the linked list starting from the head node.

3. For each node in the linked list:

a. If the address of the current node is already present in the HashSet.

b. If the address exists, there is a loop in the linked list, and the algorithm terminates, returning true.

c. If the address does not exist, add the address of the current node to the HashSet and move on to the next node.

4. If the traversal reaches the end of the linked list (i.e. the current node will becomes null ),  and there is no loop in the linked list which will terminate the algorithm and return false.

Java Code

`// Java program find loop in a linked list using Hashingimport java.util.HashSet;class ListNode {    int val;    ListNode next;    ListNode(int val) {        this.val = val;        this.next = null;    }}public class LinkedListLoopDetection {    public static boolean hasCycle(ListNode head) {        HashSet<ListNode> visitedNodes = new HashSet<>();        ListNode current = head;        while (current != null) {            if (visitedNodes.contains(current)) {                return true;            }            visitedNodes.add(current);            current = current.next;        }        return false;    }    // Example usage    public static void main(String[] args) {        // Create a linked list with a loop for testing        ListNode node1 = new ListNode(1);        ListNode node2 = new ListNode(2);        ListNode node3 = new ListNode(3);        ListNode node4 = new ListNode(4);        node1.next = node2;        node2.next = node3;        node3.next = node4;        node4.next = node2; // Loop created, node4 points back to node2        // Check if the linked list has a loop        boolean hasLoop = hasCycle(node1);        if (hasLoop) {            System.out.println("The linked list contains a loop.");        } else {            System.out.println("The linked list does not contain a loop.");        }    }}`

Output

Python Code

`#python program to find loop in linked using Hashingclass ListNode:    def __init__(self, val):        self.val = val        self.next = Nonedef hasCycle(head):    visited_nodes = set()    current = head    while current:        if current in visited_nodes:            return True        visited_nodes.add(current)        current = current.next    return False# Example usageif __name__ == "__main__":    # Create a linked list with a loop for testing    node1 = ListNode(1)    node2 = ListNode(2)    node3 = ListNode(3)    node4 = ListNode(4)    node1.next = node2    node2.next = node3    node3.next = node4    node4.next = node2  # Loop created, node4 points back to node2    # Check if the linked list has a loop    has_loop = hasCycle(node1)    if has_loop:        print("The linked list contains a loop.")    else:        print("The linked list does not contain a loop.")`

Output

C++ Code

`#include <iostream>#include <unordered_set>struct ListNode {    int val;    ListNode* next;    ListNode(int x) : val(x), next(nullptr) {}};bool hasCycle(ListNode* head) {    std::unordered_set<ListNode*> visitedNodes;    ListNode* current = head;    while (current) {        if (visitedNodes.count(current) > 0) {            return true;        }        visitedNodes.insert(current);        current = current->next;    }    return false;}// Example usageint main() {    // Create a linked list with a loop for testing    ListNode* node1 = new ListNode(1);    ListNode* node2 = new ListNode(2);    ListNode* node3 = new ListNode(3);    ListNode* node4 = new ListNode(4);    node1->next = node2;    node2->next = node3;    node3->next = node4;    node4->next = node2; // Loop created, node4 points back to node2    // Check if the linked list has a loop    bool hasLoop = hasCycle(node1);    if (hasLoop) {        std::cout << "The linked list contains a loop." << std::endl;    } else {        std::cout << "The linked list does not contain a loop." << std::endl;    }    // Clean up memory (important to avoid memory leaks)    delete node1;    delete node2;    delete node3;    delete node4;    return 0;}`

Output

Time and Space Complexity

• Time Complexity - O(N)
• Space Complexity - O(N)

Finding Loop in the Linked List  Floyd's cycle-finding algorithm

Floyd's cycle-finding algorithm  it is a simple and efficient solution to detect loops in linked lists. In this algorithm, two slow and fast pointers move through the algorithm at different speeds in the list. If there is a loop in the list, these pointers will periodically meet at some node of the Loop.

Algorithm

• To find a loop in a linked list, you need to set two pointers, slow and fast, to the beginning of the body of the linked list.
• Give the slow pointer an interval of one step and the fast pointer an interval of two steps.
• If there is a loop in the linked list, the fast pointer will overtake the slow pointer, eventually reaching some point within the Loop.
• If the fast pointer reaches the end of the linked list (i.e., it becomes null), then there is no loop in the linked list.

Java Code

`// Java program to find loop in liked listimport java.util.*;class ListNode {    int val;    ListNode next;    ListNode(int val) {        this.val = val;        this.next = null;    }}public class LinkedListLoopDetection {    public static boolean hasCycle(ListNode head) {        if (head == null || head.next == null) {            return false;        }        ListNode slow = head;        ListNode fast = head.next;        while (fast != null && fast.next != null) {            if (slow == fast) {                return true;            }            slow = slow.next;            fast = fast.next.next;        }        return false;    }    // Example usage    public static void main(String[] args) {        // Create a linked list with a loop for testing        ListNode node1 = new ListNode(1);        ListNode node2 = new ListNode(2);        ListNode node3 = new ListNode(3);        ListNode node4 = new ListNode(4);        node1.next = node2;        node2.next = node3;        node3.next = node4;        node4.next = node2; // Loop created, node4 points back to node2        // Check if the linked list has a loop        boolean hasLoop = hasCycle(node1);        if (hasLoop) {            System.out.println("The linked list contains a loop.");        } else {            System.out.println("The linked list does not contain a loop.");        }    }}`

Output

Python Code

`#python program to find loop in the linked list#Node classclass ListNode:     #Constructor to initialize     #the node object    def __init__(self, val=0, next=None):        self.val = val        self.next = nextdef has_cycle(head):    if not head or not head.next:        return False    slow = head    fast = head.next    while fast and fast.next:        if slow == fast:            return True        slow = slow.next        fast = fast.next.next    return False# Example usageif __name__ == "__main__":    # Create a linked list with a loop for testing    node1 = ListNode(1)    node2 = ListNode(2)    node3 = ListNode(3)    node4 = ListNode(4)    node1.next = node2    node2.next = node3    node3.next = node4    node4.next = node2  # Loop created, node4 points back to node2    # Check if the linked list has a loop    has_loop = has_cycle(node1)    if has_loop:        print("The linked list contains a loop.")    else:        print("The linked list does not contain a loop.")`

Output

C++ Code

`//cpp code for finding loop in linked list#include <iostream>struct ListNode {    int val;    ListNode* next;    ListNode(int x) : val(x), next(nullptr) {}};bool hasCycle(ListNode* head) {    if (!head || !head->next) {        return false;    }    ListNode* slow = head;    ListNode* fast = head->next;    while (fast && fast->next) {        if (slow == fast) {            return true;        }        slow = slow->next;        fast = fast->next->next;    }    return false;}// Example usageint main() {    // Create a linked list with a loop for testing    ListNode* node1 = new ListNode(1);    ListNode* node2 = new ListNode(2);    ListNode* node3 = new ListNode(3);    ListNode* node4 = new ListNode(4);    node1->next = node2;    node2->next = node3;    node3->next = node4;    node4->next = node2; // Loop created, node4 points back to node2    // Check if the linked list has a loop    bool has_loop = hasCycle(node1);    if (has_loop) {        std::cout << "The linked list contains a loop." << std::endl;    } else {        std::cout << "The linked list does not contain a loop." << std::endl;    }    // Clean up memory (important to avoid memory leaks)    delete node1;    delete node2;    delete node3;    delete node4;    return 0;}`

Output

Time and Space Complexity for the used algorithm

• Time Complexity - O(N)
• Space Complexity - O(1)

Note: Floyd's cycle-finding algorithm, known as the "tortoise and hair" algorithm, uses two pointers to detect loops in linked lists that move through the list at different speeds. If there is a loop in the linked list, the fast pointer will eventually catch up with the slow pointer at some node within the Loop, whereas if there is no loop, the fast pointer will reach the end of the list. The time difficulty of this algorithm is O(N), and the space difficulty is O(1).

Conclusion

In this article, we have used Floyd's cycle finding algorithm, the tortoise and hare algorithm, to find a loop in the linked list. Also, try to understand how this algorithm works. By understanding and implementing this algorithm, developers can confidently work with linked lists, knowing that their code will behave correctly with or without the Loop.