##
**
Examples
**

**Example 1:**

**Input Format**:

LL: 1 2 3 4 5

**Result**: True

**Explanation**: The last node with the value of 5 has its ‘next’ pointer pointing back to a previous node with the value of 3. This has resulted in a loop, hence we return true.

**Example 2:**

**Input Format:**

LL: 1 2 3 4 9 9

**Result: **False

**Explanation**: : In this example, the linked list does not have a loop hence returns false.

**Practice:**

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

## Brute Force Approach

## Algorithm / Intuition

A **loop** in a linked list occurs when there’s a node that, **when followed**, **brings you back** to it, indicating a **closed loop** in the list.

Hence it’s important to keep track of nodes that have already been visited so that loops can be detected. One common way to do this is by using hashing.

**Algorithm:**

**Step 1: Traverse** through the LL using the traversal technique of assigning a **temp** node to the head and **iterating** by moving to the next element till we reach **null**.

**Step 2: **While traversing, keep a track of the visited nodes in the map data structure.

**Note: **Storing the entire node in the map is essential to distinguish between nodes with **identical values** but **different positions** in the list. This ensures **accurate loop detection** and not just duplicate value checks.

**Step 3:** If a **previously** **visited** **node** is encountered again, that proves that there is a **loop** in the linked list hence return **true**.

**Step 4:** If the traversal is completed, and we reach the last point of the LL which is **null**, it means there was **noloop**, hence we return **false**.

## Code

```
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Node class represents a
// node in a linked list
class Node {
public:
// Data stored in the node
int data;
// Pointer to the next node in the list
Node* next;
// Constructor with both data
// and next node as parameters
Node(int data1, Node* next1) {
data = data1;
next = next1;
}
// Constructor with only data as
// a parameter, sets next to nullptr
Node(int data1) {
data = data1;
next = nullptr;
}
};
// function to detect loop in linked list
bool detectLoop(Node* head) {
// Initialize a pointer 'temp'
// at the head of the linked list
Node* temp = head;
// Create a map to keep track of
// encountered nodes
std::unordered_map<Node*, int> nodeMap;
// Step 2: Traverse the linked list
while (temp != nullptr) {
// If the node is already in the
// map, there is a loop
if (nodeMap.find(temp) != nodeMap.end()) {
return true;
}
// Store the current node
// in the map
nodeMap[temp] = 1;
// Move to the next node
temp = temp->next;
}
// Step 3: If the list is successfully traversed
// without a loop, return false
return false;
}
int main() {
// Create a sample linked list
// with a loop for testing
Node* head = new Node(1);
Node* second = new Node(2);
Node* third = new Node(3);
Node* fourth = new Node(4);
Node* fifth = new Node(5);
head->next = second;
second->next = third;
third->next = fourth;
fourth->next = fifth;
// Create a loop
fifth->next = third;
// Check if there is a loop
// n the linked list
if (detectLoop(head)) {
cout << "Loop detected in the linked list." << endl;
} else {
cout << "No loop detected in the linked list." << endl;
}
// Clean up memory (free the allocated nodes)
delete head;
delete second;
delete third;
delete fourth;
delete fifth;
return 0;
}
```

```
import java.util.HashMap;
import java.util.Map;
// Node class represents a
// node in a linked list
class Node {
// Data stored in the node
public int data;
// Pointer to the next node in the list
public Node next;
// Constructor with both data
// and next node as parameters
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
// Constructor with only data as
// a parameter, sets next to null
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
// Function to detect a
// loop in a linked list
public static boolean detectLoop(Node head) {
// Initialize a pointer 'temp'
// at the head of the linked list
Node temp = head;
// Create a map to keep track
// of encountered nodes
Map<Node, int> nodeMap = new HashMap<>();
// Step 2: Traverse the linked list
while (temp != null) {
// If the node is already in
// the map, there is a loop
if (nodeMap.containsKey(temp)) {
return true;
}
// Store the current node in the map
nodeMap.put(temp, 1);
// Move to the next node
temp = temp.next;
}
// Step 3: If the list is successfully
// traversed without a loop, return false
return false;
}
public static void main(String[] args) {
// Create a sample linked list
// with a loop for testing
Node head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
Node fifth = new Node(5);
head.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
// Create a loop
fifth.next = third;
// Check if there is a loop
// in the linked list
if (detectLoop(head)) {
System.out.println("Loop detected in the linked list.");
} else {
System.out.println("No loop detected in the linked list.");
}
// No need to explicitly free memory
// in Java; the garbage collector handles it
}
}
```

```
# Node class represents
# a node in a linked list
class Node:
def __init__(self, data, next_node=None):
self.data = data
self.next = next_node
# Function to detect a loop
# n a linked list
def detect_loop(head):
# Initialize a pointer 'temp' at
# the head of the linked list
temp = head
# Create a set to keep track
# of encountered nodes
node_set = set()
# Step 2: Traverse the linked list
while temp is not None:
# If the node is already
# in the set, there is a loop
if temp in node_set:
return True
# Store the current node in the set
node_set.add(temp)
# Move to the next node
temp = temp.next
# Step 3: If the list is successfully
# traversed without a loop, return False
return False
if __name__ == "__main__":
# Create a sample linked list with
# a loop for testing
head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
fifth = Node(5)
head.next = second
second.next = third
third.next = fourth
fourth.next = fifth
# Create a loop
fifth.next = third
# Check if there is a loop
# in the linked list
if detect_loop(head):
print("Loop detected in the linked list.")
else:
print("No loop detected in the linked list.")
# No need to explicitly free memory
# in Python; memory management is automatic
```

```
// Node class represents a
// node in a linked list
class Node {
constructor(data, next) {
// Data stored in the node
this.data = data;
// Pointer to the next node in the list
this.next = next;
}
}
// Function to detect a loop
// in a linked list
function detectLoop(head) {
// Initialize a pointer 'temp'
// at the head of the linked list
let temp = head;
// Create a map to keep track of encountered nodes
const nodeMap = new Map();
// Step 2: Traverse the linked list
while (temp !== null) {
// If the node is already in
// the map, there is a loop
if (nodeMap.has(temp)) {
return true;
}
// Store the current node in the map
nodeMap.set(temp, true);
// Move to the next node
temp = temp.next;
}
// Step 3: If the list is successfully
// traversed without a loop, return false
return false;
}
// Create a sample linked list
// with a loop for testing
const head = new Node(1);
const second = new Node(2);
const third = new Node(3);
const fourth = new Node(4);
const fifth = new Node(5);
head.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
// Create a loop
fifth.next = third;
// Check if there is a loop in the linked list
if (detectLoop(head)) {
console.log("Loop detected in the linked list.");
} else {
console.log("No loop detected in the linked list.");
}
```

**Output:**
Loop detected in the linked list.

## Complexity Analysis

**Time Complexity: O(N * 2 * log(N) )**The algorithm traverses the linked list **once**, performing hashmap **insertions** and **searches** in the while loop for each node. The insertion and search operations in the unordered_map have a worst-case time complexity of **O(log(N))**. As the loop iterates through N nodes, the total time complexity is determined by the product of the traversal **(O(N))** and the average-case complexity of the **hashmap operations (insert and search)**, resulting in **O(N * 2 * log(N)). **

Hashmaps and their time complexities are discussed in more detail here.

**Space Complexity: O(N) **The code uses a **hashmap**/**dictionary** to store encountered nodes, which can take up to O(N) additional space, where ‘n’ is the number of nodes in the list. Hence, the **spacecomplexity** is O(N) due to the use of the map to track nodes.

## Optimal Approach

## Algorithm / Intuition

The previous method uses O(N) **additional** **memory**, which can become quite large as the **linked** **list** **length** **grows**. To enhance efficiency, the **Tortoise** and **Hare** **Algorithm** is introduced as an **optimization**.

The Tortoise and Hare approach has been discussed in this **article**.

When the **tortoise** and **hare** enter the loop, they may be at different positions within the loop due to the difference in their **speeds**. The hare is moving **faster**, so it will traverse a **greater** **distance** in the same amount of time.

If there is **no loop** in the linked list, the hare will eventually reach the **end**, and the algorithm will terminate without a meeting occurring.

**Algorithm**

**Step 1:** Initialise two pointers, **`slow`** and **`fast`**, to the head of the linked list. **`slow`** will advance **one** **step** at a time, while **`fast`** will advance **two** **steps** at a time. These pointers will move **simultaneously**.

**Step 2: **Traverse the linked list with the **`slow`** and **`fast`** pointers. While traversing, repeatedly move **`slow`** **one** **step** and **`fast`** **two** **steps** at a time.

**Step 3: **Continue this traversal until one of the following conditions is met:

**`fast**` or**`fast.next`**reaches the end of the linked list (i.e., becomes**null**). In this case, there is**no loop**in the linked list ie. the linked list is**linear**, and the algorithm terminates by returning**false**.**`fast`**and**`slow`**pointers meet at the same node. This indicates the presence of a**loop**in the linked list, and the algorithm terminates by returning**`true`**.

**Intuition: **

In a linked list with a loop, consider two pointers: one that moves one node at a time (**slow**) and another that moves two nodes at a time (**fast**). If we start moving these pointers with their defined speed they will surely enter the loop and might be at some distance **‘d’** from each other within the loop.

The key insight here is the **relative** **speed** between these pointers. The fast pointer, moving at double the speed of the slow one, **closes** **the** **gap** between them by **one** **node** **in** **every** **iteration**. This means that with each step, the distance decreases by one node.

Imagine a race where one runner moves at **twice** the speed of another. The faster runner covers the ground faster and closes the gap, resulting in a reduction in the distance between them. Similarly, the **fast** pointer catches up to the **slow** pointer in the looped linked list, closing in the gap between them until it reaches zero.

**Proof: **

Let **‘d’** denote the initial distance between the **slow** and **fast** pointers inside the loop. At each step, the fast pointer moves ahead by two nodes while the slow pointer advances by one node.

The **relative** **speed** between them causes the gap to decrease by one node in each iteration (fast gains two nodes while slow gains one node). This continuous reduction ensures that the difference between their positions **decreases** **steadily**. Mathematically, if the fast pointer **gains ground** twice as fast as the slow pointer, the difference in their positions reduces by one node after each step. Consequently, this reduction in the distance between them continues **until** the** difference becomes zero**.

Hence, the proof lies in this **iterative** **process** where the faster rate of the fast pointer leads to a continual decrease in the gap distance, ultimately resulting in their collision within the looped linked list.

## Code

```
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Node class represents a
// node in a linked list
class Node {
public:
// Data stored in the node
int data;
// Pointer to the next node in the list
Node* next;
// Constructor with both data
// and next node as parameters
Node(int data1, Node* next1) {
data = data1;
next = next1;
}
// Constructor with only data as
// a parameter, sets next to nullptr
Node(int data1) {
data = data1;
next = nullptr;
}
};
// Function to detect a loop in a linked
// list using the Tortoise and Hare Algorithm
bool detectCycle(Node* head) {
// Initialize two pointers, slow and fast,
// to the head of the linked list
Node* slow = head;
Node* fast = head;
// Step 2: Traverse the linked list with
// the slow and fast pointers
while (fast != nullptr && fast->next != nullptr) {
// Move slow one step
slow = slow->next;
// Move fast two steps
fast = fast->next->next;
// Check if slow and fast pointers meet
if (slow == fast) {
return true; // Loop detected
}
}
// If fast reaches the end of the list,
// there is no loop
return false;
}
int main() {
// Create a sample linked list
// with a loop for testing
Node* head = new Node(1);
Node* second = new Node(2);
Node* third = new Node(3);
Node* fourth = new Node(4);
Node* fifth = new Node(5);
head->next = second;
second->next = third;
third->next = fourth;
fourth->next = fifth;
// Create a loop
fifth->next = third;
// Check if there is a loop
// n the linked list
if (detectCycle(head)) {
cout << "Loop detected in the linked list." << endl;
} else {
cout << "No loop detected in the linked list." << endl;
}
// Clean up memory (free the allocated nodes)
delete head;
delete second;
delete third;
delete fourth;
delete fifth;
return 0;
}
```

```
import java.util.HashMap;
import java.util.Map;
// Node class represents a
// node in a linked list
class Node {
// Data stored in the node
public int data;
// Pointer to the next node in the list
public Node next;
// Constructor with both data
// and next node as parameters
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
// Constructor with only data as
// a parameter, sets next to null
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
// Function to detect a loop in a linked list
// using the Tortoise and Hare Algorithm
public static boolean detectCycle(Node head) {
// Initialize two pointers, slow and fast,
// to the head of the linked list
Node slow = head;
Node fast = head;
// Step 2: Traverse the linked list
// with the slow and fast pointers
while (fast != null && fast.next != null) {
// Move slow one step
slow = slow.next;
// Move fast two steps
fast = fast.next.next;
// Check if slow and fast pointers meet
if (slow == fast) {
return true; // Loop detected
}
}
// If fast reaches the end of the
// list, there is no loop
return false;
}
public static void main(String[] args) {
// Create a sample linked list
// with a loop for testing
Node head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
Node fifth = new Node(5);
head.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
// Create a loop
fifth.next = third;
// Check if there is a loop
// in the linked list
if (detectCycle(head)) {
System.out.println("Loop detected in the linked list.");
} else {
System.out.println("No loop detected in the linked list.");
}
// No need to explicitly free memory
// in Java; the garbage collector handles it
}
}
```

```
# Node class represents
# a node in a linked list
class Node:
def __init__(self, data, next_node=None):
self.data = data
self.next = next_node
# Function to detect a loop in a
# linked list using the Tortoise and Hare Algorithm
def detect_cycle(head):
# Initialize two pointers, slow and fast,
# to the head of the linked list
slow = head
fast = head
# Step 2: Traverse the linked list
# with the slow and fast pointers
while fast is not None and fast.next is not None:
# Move slow one step
slow = slow.next
# Move fast two steps
fast = fast.next.next
# Check if slow and fast pointers meet
if slow == fast:
return True # Loop detected
# If fast reaches the end of the
# list, there is no loop
return False
if __name__ == "__main__":
# Create a sample linked list with
# a loop for testing
head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
fifth = Node(5)
head.next = second
second.next = third
third.next = fourth
fourth.next = fifth
# Create a loop
fifth.next = third
# Check if there is a loop
# in the linked list
if detect_cycle(head):
print("Loop detected in the linked list.")
else:
print("No loop detected in the linked list.")
# No need to explicitly free memory
# in Python; memory management is automatic
```

```
// Node class represents a
// node in a linked list
class Node {
constructor(data, next) {
// Data stored in the node
this.data = data;
// Pointer to the next node in the list
this.next = next;
}
}
// Function to detect a loop in a linked list
// using the Tortoise and Hare Algorithm
function detectCycle(head) {
// Initialize two pointers, slow and fast,
// to the head of the linked list
let slow = head;
let fast = head;
// Step 2: Traverse the linked list
// with the slow and fast pointers
while (fast !== null && fast.next !== null) {
// Move slow one step
slow = slow.next;
// Move fast two steps
fast = fast.next.next;
// Check if slow and fast pointers meet
if (slow === fast) {
return true; // Loop detected
}
}
// If fast reaches the end of the list, there is no loop
return false;
}
// Create a sample linked list
// with a loop for testing
const head = new Node(1);
const second = new Node(2);
const third = new Node(3);
const fourth = new Node(4);
const fifth = new Node(5);
head.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
// Create a loop
fifth.next = third;
// Check if there is a loop in the linked list
if (detectCycle(head)) {
console.log("Loop detected in the linked list.");
} else {
console.log("No loop detected in the linked list.");
}
```

**Output:**
Loop detected in the linked list.

## Complexity Analysis

**Time Complexity: O(N)**, where N is the number of nodes in the linked list. This is because in the **worst-case scenario**, the **fast** pointer, which **moves** **quicker**, will either reach the end of the list (in case of no loop) or meet the **slow** pointer (in case of a loop) in a **linear time** relative to the length of the list.

The key insight into why this is **O(N)** and **not something slower** is that each step of the algorithm reduces the distance between the fast and slow pointers (when they are in the loop) by one. Therefore, the **maximum** **number** of **steps** needed for them to meet is **proportional** to the number of nodes in the list.

**Space Complexity : O(1)** The code uses only a **constantamount** of **additionalspace**, regardless of the linked list’s length. This is achieved by using two pointers (**slow** and **fast**) to detect the loop without any significant extra memory usage, resulting in **constantspace** complexity, O(1).

## Video Explanation

In case you are learning DSA, you should check out our free A2Z DSA Course with videos and blogs.

Special thanks toGauri Tomarfor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article