Different techniques for Detecting and Removing Loops in Linked Lists

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. node 3.
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. node 1.

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. Return null.
- 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 a loop is found, remove it by setting the next pointer of the previous node to null.
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.")


#include <iostream>
#include <unordered_set>
using namespace std;

// Definition of the Node class for the linked list
class Node {
public:
  int data;
  Node* next;
  
  Node(int data) {
    this->data = data;
    this->next = nullptr;
  }
};

// Helper function to create a linked list
Node* create_linked_list(int values[], int size) {
  if (size == 0) {
    return nullptr;
  }
  Node* head = new Node(values[0]);
  Node* current = head;
  for (int i = 1; i < size; i++) {
    current->next = new Node(values[i]);
    current = current->next;
  }
  return head;
}

// Helper function to print linked list
void print_linked_list(Node* head) {
  Node* current = head;
  while (current) {
    cout << current->data << " -> ";
    current = current->next;
  }
  cout << "None" << endl;
}

// Function to detect and remove loop in a linked list
Node* detect_and_remove_loop(Node* head) {
  // Step 1: Initialize an empty hash set to store visited nodes
  unordered_set<Node*> visited_nodes;
  
  // Step 2: Start traversing the linked list from the head node
  Node* current = head;
  Node* previous = nullptr;
  
  // Step 3: Traverse the linked list
  while (current) {
    // If the node is already in the hash set, we've found a loop
    if (visited_nodes.find(current) != visited_nodes.end()) {
      // Step 4: Remove the loop by setting the next pointer of the previous node to nullptr
      previous->next = nullptr;
      // 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.insert(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 nullptr as no loop was found
  return nullptr;
}

// Function to free the memory allocated for the linked list
void free_linked_list(Node* head) {
  Node* current = head;
  while (current) {
    Node* temp = current;
    current = current->next;
    delete temp;
  }
}

int main() {
  // Create a linked list with a loop: 1 -> 2 -> 3 -> 4 -> 5 -> 3
  int values[] = {1, 2, 3, 4, 5};
  Node* head = create_linked_list(values, 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
  Node* loop_start = detect_and_remove_loop(head);

  if (loop_start) {
    cout << "Loop is detected and removed." << endl;
    cout << "Loop started at node with value: " << loop_start->data << endl;
    cout << "Linked list after removing the loop:" << endl;
    print_linked_list(head);
  } else {
    cout << "No loop detected in the linked list." << endl;
  }

  // Free the memory allocated for the linked list
  free_linked_list(head);

  return 0;
}


// Definition of the Node class for the linked list
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// Helper function to create a linked list
function createLinkedList(values) {
  if (!values.length) {
    return null;
  }
  let head = new Node(values[0]);
  let current = head;
  for (let i = 1; i < values.length; i++) {
    current.next = new Node(values[i]);
    current = current.next;
  }
  return head;
}

// Helper function to print linked list
function printLinkedList(head) {
  let current = head;
  let result = '';
  while (current) {
    result += current.data + ' -> ';
    current = current.next;
  }
  result += 'None';
  console.log(result);
}

// Function to detect and remove loop in a linked list
function detectAndRemoveLoop(head) {
  // Step 1: Initialize an empty Set to store visited nodes
  let visitedNodes = new Set();
  
  // Step 2: Start traversing the linked list from the head node
  let current = head;
  let previous = null;
  
  // Step 3: Traverse the linked list
  while (current) {
    // If the node is already in the Set, we've found a loop
    if (visitedNodes.has(current)) {
      // Step 4: Remove the loop by setting the next pointer of the previous node to null
      previous.next = null;
      // Step 5: Return the node where the loop starts
      return current;
    }
    
    // If the node is not in the Set, add it to the Set
    visitedNodes.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 null as no loop was found
  return null;
}

// Create a linked list with a loop: 1 -> 2 -> 3 -> 4 -> 5 -> 3
let head = createLinkedList([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
let loopStart = detectAndRemoveLoop(head);

if (loopStart) {
  console.log("Loop is detected and removed.");
  console.log(`Loop started at node with value: ${loopStart.data}`);
  console.log("Linked list after removing the loop:");
  printLinkedList(head);
} else {
  console.log("No loop detected in the linked list.");
}


import java.util.*;

public class Main {
  // Definition of the Node class for the linked list
  static class Node {
    int data;
    Node next;
    
    Node(int data) {
      this.data = data;
      this.next = null;
    }
  }

  // Helper function to create a linked list
  static Node createLinkedList(int[] values) {
    if (values == null || values.length == 0) {
      return null;
    }
    Node head = new Node(values[0]);
    Node current = head;
    for (int i = 1; i < values.length; i++) {
      current.next = new Node(values[i]);
      current = current.next;
    }
    return head;
  }

  // Helper function to print linked list
  static void printLinkedList(Node head) {
    Node current = head;
    while (current != null) {
      System.out.print(current.data + " -> ");
      current = current.next;
    }
    System.out.println("null");
  }

  // Function to detect and remove loop in a linked list
  static Node detectAndRemoveLoop(Node head) {
    // Step 1: Initialize an empty hash set to store visited nodes
    Set<Node> visitedNodes = new HashSet<>();
    
    // Step 2: Start traversing the linked list from the head node
    Node current = head;
    Node previous = null;
    
    // Step 3: Traverse the linked list
    while (current != null) {
      // If the node is already in the hash set, we've found a loop
      if (visitedNodes.contains(current)) {
        // Step 4: Remove the loop by setting the next pointer of the previous node to null
        previous.next = null;
        // 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
      visitedNodes.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 null as no loop was found
    return null;
  }

  public static void main(String[] args) {
    // Create a linked list with a loop: 1 -> 2 -> 3 -> 4 -> 5 -> 3
    Node head = createLinkedList(new int[]{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
    Node loopStart = detectAndRemoveLoop(head);

    if (loopStart != null) {
      System.out.println("Loop is detected and removed.");
      System.out.println("Loop started at node with value: " + loopStart.data);
      System.out.println("Linked list after removing the loop:");
      printLinkedList(head);
    } else {
      System.out.println("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 to false 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. Return null.
- If the node’s visited flag is true, we’ve found a loop. This node is the start of the loop.
- If the node’s visited flag is false, set it to true and move to the next node. Also keep track of the previous node.
If a loop is found, remove it by setting the next pointer of the previous node to null.
Reset all visited flags back to false 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.")


#include <iostream>
#include <vector>

using namespace std;

class Node {
public:
  int data;
  Node* next;
  bool visited;

  Node(int value) : data(value), next(nullptr), visited(false) {}
};

// Helper function to create a linked list
Node* create_linked_list(const vector<int>& values) {
  if (values.empty()) {
    return nullptr;
  }
  Node* head = new Node(values[0]);
  Node* current = head;
  for (size_t i = 1; i < values.size(); ++i) {
    current->next = new Node(values[i]);
    current = current->next;
  }
  return head;
}

// Helper function to print linked list
void print_linked_list(Node* head) {
  Node* current = head;
  while (current) {
    cout << current->data << " -> ";
    current = current->next;
  }
  cout << "None" << endl;
}

// Helper function to free memory allocated for linked list
void free_linked_list(Node* head) {
  Node* current = head;
  while (current) {
    Node* temp = current;
    current = current->next;
    delete temp;
  }
}

Node* detect_and_remove_loop(Node* head) {
  if (!head) {
    return nullptr;
  }

  Node* current = head;
  Node* prev = nullptr;
  Node* loop_start = nullptr;

  // 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 = nullptr;
  }

  // Reset visited flags
  current = head;
  while (current) {
    current->visited = false;
    current = current->next;
  }

  return loop_start;
}

int main() {
  // Create a linked list with a loop: 1 -> 2 -> 3 -> 4 -> 5 -> 3
  Node* 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
  Node* loop_start = detect_and_remove_loop(head);

  if (loop_start) {
    cout << "Loop is detected and removed." << endl;
    cout << "Loop started at node with value: " << loop_start->data << endl;
    cout << "Linked list after removing the loop:" << endl;
    print_linked_list(head);
  } else {
    cout << "No loop detected in the linked list." << endl;
  }

  // Free memory
  free_linked_list(head);

  return 0;
}


// Node class definition
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.visited = false;
  }
}

// Helper function to create a linked list
function createLinkedList(values) {
  if (!values.length) {
    return null;
  }
  let head = new Node(values[0]);
  let current = head;
  for (let i = 1; i < values.length; i++) {
    current.next = new Node(values[i]);
    current = current.next;
  }
  return head;
}

// Helper function to print linked list
function printLinkedList(head) {
  let current = head;
  let result = '';
  while (current) {
    result += current.data + ' -> ';
    current = current.next;
  }
  result += 'None';
  console.log(result);
}

function detectAndRemoveLoop(head) {
  if (!head) {
    return null;
  }

  let current = head;
  let prev = null;
  let loopStart = null;

  // Traverse the list and detect loop
  while (current) {
    if (current.visited) {
      loopStart = current;
      break;
    }
    current.visited = true;
    prev = current;
    current = current.next;
  }

  // If loop is found, remove it
  if (loopStart) {
    prev.next = null;
  }

  // Reset visited flags
  current = head;
  while (current) {
    current.visited = false;
    current = current.next;
  }

  return loopStart;
}

// Create a linked list with a loop: 1 -> 2 -> 3 -> 4 -> 5 -> 3
let head = createLinkedList([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
let loopStart = detectAndRemoveLoop(head);

if (loopStart) {
  console.log("Loop is detected and removed.");
  console.log(`Loop started at node with value: ${loopStart.data}`);
  console.log("Linked list after removing the loop:");
  printLinkedList(head);
} else {
  console.log("No loop detected in the linked list.");
}


public class Main {
  static class Node {
    int data;
    Node next;
    boolean visited;

    Node(int data) {
      this.data = data;
      this.next = null;
      this.visited = false;
    }
  }

  // Helper function to create a linked list
  static Node createLinkedList(int[] values) {
    if (values == null || values.length == 0) {
      return null;
    }
    Node head = new Node(values[0]);
    Node current = head;
    for (int i = 1; i < values.length; i++) {
      current.next = new Node(values[i]);
      current = current.next;
    }
    return head;
  }

  // Helper function to print linked list
  static void printLinkedList(Node head) {
    Node current = head;
    while (current != null) {
      System.out.print(current.data + " -> ");
      current = current.next;
    }
    System.out.println("null");
  }

  static Node detectAndRemoveLoop(Node head) {
    if (head == null) {
      return null;
    }

    Node current = head;
    Node prev = null;
    Node loopStart = null;

    // Traverse the list and detect loop
    while (current != null) {
      if (current.visited) {
        loopStart = current;
        break;
      }
      current.visited = true;
      prev = current;
      current = current.next;
    }

    // If loop is found, remove it
    if (loopStart != null) {
      prev.next = null;
    }

    // Reset visited flags
    current = head;
    while (current != null) {
      current.visited = false;
      current = current.next;
    }

    return loopStart;
  }

  public static void main(String[] args) {
    // Create a linked list with a loop: 1 -> 2 -> 3 -> 4 -> 5 -> 3
    Node head = createLinkedList(new int[]{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
    Node loopStart = detectAndRemoveLoop(head);

    if (loopStart != null) {
      System.out.println("Loop is detected and removed.");
      System.out.println("Loop started at node with value: " + loopStart.data);
      System.out.println("Linked list after removing the loop:");
      printLinkedList(head);
    } else {
      System.out.println("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 Cycle-Finding Algorithm (Tortoise and Hare)

Floyd’s Cycle-Finding 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) and fast (hare), to the head of the linked list.
Move the slow pointer one step and the fast 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 the slow 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 to null.

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 long-running applications.