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.