Detecting loops or cycles in a linked list refers to the process of determining whether the last node of the linked list points to some other previous node in the linked list. In a normal linked list, each node has a reference to the next node in sequence, and the last node points to null
. However, if there’s a loop, one of the nodes (tail node) points back to a previous node, creating a loop or cycle in the linked list.
Here’s a simple example of a linked list with a loop:
In this example, the tail node node containing 5
points back to the node containing 3
, creating a loop. If we try to traverse or iterate this list, we will end up visiting nodes in the sequence 1, 2, 3, 4, 5, 3, 4, 5, 3, 4, 5, and so on, infinitely. Detecting and removing loops in a linked list is important for preventing infinite traversals and maintaining data integrity.
Prerequisites: Basics of Linked List Data Structure, Creating and Connecting Nodes in a Linked List, Traverse and Print all values present in a Linked List Data Structure.
Problem Statement
Given a linked list, determine whether it contains a cycle or loop. If a loop exists, identify the node where the loop begins and break the loop.
 Input: Head node of a linked list.
 Output: If there is a loop, remove the loop and return the node where the loop starts. Otherwise return
null
.
Example Inputs and Outputs:
 Linked list without a loop/cycle: The function should return
null
as there is no loop.

Linked list with a loop/cycle: The function should remove the loop made up of nodes
3, 4, 5
and return the node where the loop starts i.e. node3
. 
Linked list with a loop/cycle at the head node: The function should remove the loop made up of nodes
1, 2, 3, 4, 5
and return the node where the loop starts i.e. node1
.
Challenges & Considerations
 Basic Linked List traversal doesn’t work: Simply traversing the linked list and checking for the end (
null
) fails because the loop creates an infinite sequence of nodes.  Memory constraints: Storing all visited nodes to check for repetition may not be feasible for large lists due to memory limitations.
 Preserving the original list: Some solutions might require modifying the list structure, which may not always be acceptable.
 Performance considerations: The solution should ideally have linear time complexity and constant space complexity for efficiency.
 Detecting the start of the loop: While identifying the existence of a loop is one challenge, pinpointing where the loop begins adds another layer of complexity.
Various Techniques for Detecting Loops
Hashing Method
The Hashing Method is a straightforward approach to detect loops in a linked list and remove them. It uses a hash table (or set) to keep track of visited nodes. As we traverse the list, we check if each node has been seen before by looking up entries in the hash table and use this info to break the loop.
Algorithm steps:
 Initialize an empty hash set to store visited nodes.
 Start traversing the linked list from the head node.
 For each node:
 If the node is
null
, we’ve reached the end of the list without finding a loop. Returnnull
.  If the node is already in the hash set, we’ve found a loop. This node is the start of the loop. We can stop processing next nodes.
 If the node is not in the hash set, add it to the set and move to the next node. Also keep track of the previous node.
 If the node is
 If a loop is found, remove it by setting the
next
pointer of the previous node tonull
.  Return the node where the loop starts (or
null
if no loop is found).
Time Complexity: O(n)
, where n
is the number of nodes in the linked list. We traverse each node once.
Space Complexity: O(n)
space for storing references to all visited nodes in a hash table or set.
Below is the implementation of this approach in various programming languages:
# Definition of the Node class for the linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Helper function to create a linked list
def create_linked_list(values):
if not values:
return None
head = Node(values[0])
current = head
for value in values[1:]:
current.next = Node(value)
current = current.next
return head
# Helper function to print linked list
def print_linked_list(head):
current = head
while current:
print(current.data, end=" > ")
current = current.next
print("None")
# Function to detect and remove loop in a linked list
def detect_and_remove_loop(head):
# Step 1: Initialize an empty hash set to store visited nodes
visited_nodes = set()
# Step 2: Start traversing the linked list from the head node
current = head
previous = None
# Step 3: Traverse the linked list
while current:
# If the node is already in the hash set, we've found a loop
if current in visited_nodes:
# Step 4: Remove the loop by setting the next pointer of the previous node to None
previous.next = None
# Step 5: Return the node where the loop starts
return current
# If the node is not in the hash set, add it to the set
visited_nodes.add(current)
# Move to the next node
previous = current
current = current.next
# If we've reached here, we've traversed the entire list without finding a loop
# Step 5: Return None as no loop was found
return None
# Create a linked list with a loop: 1 > 2 > 3 > 4 > 5 > 3
head = create_linked_list([1, 2, 3, 4, 5])
# Create a loop by connecting the last node (5) to the third node (3)
head.next.next.next.next.next = head.next.next
# Detect and remove the loop
loop_start = detect_and_remove_loop(head)
if loop_start:
print("Loop is detected and removed.")
print(f"Loop started at node with value: {loop_start.data}")
print("Linked list after removing the loop:")
print_linked_list(head)
else:
print("No loop detected in the linked list.")
This method is simple to implement and understand, but it requires additional space proportional to the size of the linked list, which might be a concern for very large lists.
Marking Visited Nodes
The Marking Visited Nodes method is a simple approach that modifies the linked list structure to detect and remove loops. This technique requires a boolean attribute visited
to be defined on the linked list node structure. This attribute is used to mark nodes as we traverse the list and check if we encountered an already visited node again.
Algorithm steps:
 Modify the linked list node structure to include a boolean
visited
flag, initialized tofalse
for all nodes.  Start traversing the linked list from the head node.
 For each node:
 If the node is
null
, we’ve reached the end of the list without finding a loop. Returnnull
.  If the node’s
visited
flag istrue
, we’ve found a loop. This node is the start of the loop.  If the node’s
visited
flag isfalse
, set it totrue
and move to the next node. Also keep track of the previous node.
 If the node is
 If a loop is found, remove it by setting the
next
pointer of the previous node tonull
.  Reset all
visited
flags back tofalse
by traversing the list again.  Return the node where the loop starts (or
null
if no loop is found).
Time Complexity: O(n)
, where n
is the number of nodes in the linked list. We need traverse the list twice: once to detect the loop and once to reset the flags.
Space Complexity: O(n)
, as we need space for storing n
visited flags corresponding to each node in the linked list. Although not constant space, this approach uses much less space than the hashing approach.
Below is the implementation of this approach:
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.visited = False
# Helper function to create a linked list
def create_linked_list(values):
if not values:
return None
head = Node(values[0])
current = head
for value in values[1:]:
current.next = Node(value)
current = current.next
return head
# Helper function to print linked list
def print_linked_list(head):
current = head
while current:
print(current.data, end=" > ")
current = current.next
print("None")
def detect_and_remove_loop(head):
if not head:
return None
current = head
prev = None
loop_start = None
# Traverse the list and detect loop
while current:
if current.visited:
loop_start = current
break
current.visited = True
prev = current
current = current.next
# If loop is found, remove it
if loop_start:
prev.next = None
# Reset visited flags
current = head
while current:
current.visited = False
current = current.next
return loop_start
# Create a linked list with a loop: 1 > 2 > 3 > 4 > 5 > 3
head = create_linked_list([1, 2, 3, 4, 5])
# Create a loop by connecting the last node (5) to the third node (3)
head.next.next.next.next.next = head.next.next
# Detect and remove the loop
loop_start = detect_and_remove_loop(head)
if loop_start:
print("Loop is detected and removed.")
print(f"Loop started at node with value: {loop_start.data}")
print("Linked list after removing the loop:")
print_linked_list(head)
else:
print("No loop detected in the linked list.")
This method is efficient in terms of space usage and is relatively easy to implement. However, it requires modifying the linked list structure, which may not always be feasible or desirable in all scenarios.
Floyd’s CycleFinding Algorithm (Tortoise and Hare)
Floyd’s CycleFinding Algorithm, also known as the “Tortoise and Hare” algorithm, is an elegant and efficient method for detecting loops in a linked list. This algorithm uses two pointers moving at different speeds to detect a cycle without modifying the list structure or using additional space.
Algorithm steps:
 Initialize two pointers,
slow
(tortoise) andfast
(hare), to the head of the linked list.  Move the
slow
pointer one step and thefast
pointer two steps at a time through the list.  If there’s no cycle, the
fast
pointer will reach the end of the list (null
).  If there’s a cycle, the
fast
pointer will eventually meet theslow
pointer inside the loop.  Once they meet, reset the
slow
pointer to the head of the list.  Move both pointers one step at a time until they meet again. The meeting point is the start of the loop.
 To remove the loop, set the
next
pointer of the last node in the loop tonull
.
Time Complexity: O(n)
, where n
is the number of nodes in the linked list. In the worst case, we might need to traverse the entire list once to detect the cycle and once more to find the start of the loop.
Space Complexity: O(1)
, as we only use two pointers regardless of the list size.
For more details about the logic behind this algorithm and implementation details, visit this article: Floyd’s Tortise and Hare Cycle Finding Algorithm
This algorithm is highly efficient in terms of both time and space complexity. It doesn’t require any modification to the list structure or additional data structures, making it versatile and widely applicable.
Reversal Method (Detection Only)
The Reversal Method is a unique approach to detect loops in a linked list. Unlike other methods, this technique doesn’t remove the loop but only detects its presence. It works by reversing the linked list and checking if the last node after reversal is the same as the original head node.
Algorithm steps:
 Store the original head node of the linked list.
 Reverse the entire linked list.
 Compare the last node (new head after reversal) with the original head node:
 If they are the same, it means that a loop or cycle exists in the linked list.
 If they are different, there is no loop in the linked list.
 Reverse the linked list again to restore its original order.
Time Complexity: O(n)
, where n
is the number of nodes in the linked list. We traverse the list twice to reverse it.
Space Complexity: O(1)
, as we only use a constant amount of extra space regardless of the list size.
This method is interesting because it detects loops without using extra space or modifying the node structure. However, it has some limitations:
 It doesn’t identify the start of the loop.
 It temporarily modifies the list structure (though it’s restored at the end).
 It might not be suitable for concurrent environments where the list shouldn’t be modified.
Applications
Below are some of the applications of detecting loops or cycles in a linked list data structure and removing them:
 Preventing Infinite Loops: Ensures algorithm termination by detecting cycles, crucial for robust software systems and data processing pipelines.
 Ensuring Data Integrity: Maintains data structure correctness by identifying unintended cycles, critical in database and file systems to prevent data corruption.
 Cycle Detection in Graphs: Extends linked list loop detection techniques to graphs, useful for network analysis, deadlock detection, and dependency resolution.
 Garbage Collection: Essential for identifying and collecting circular references in languages with automatic memory management, preventing memory leaks in longrunning applications.