# Find Loop in Linked List

## 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.

## What is Linked List

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 Hashing

import 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 Hashing

class ListNode:

def __init__(self, val):

self.val = val

self.next = None

def 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 usage

if __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 usage

int 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 list

import 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 class

class ListNode:

#Constructor to initialize

#the node object

def __init__(self, val=0, next=None):

self.val = val

self.next = next

def 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 usage

if __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 usage

int 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.