Approach 1- Using Hashing – O(N) Time and O(N) Space
Traverse through the Linked List and while traversing insert each node into the hash set. Also, maintain a prev pointer which points to the previous node of the current node. If there is a loop present in the Linked List, there will be a node which will be already present in the hash set.
- If there is a node which is already present in the hash set, then update the next pointer of prev to NULL to remove the loop from the linked list.
- Else, If there is no node which is already present in the hash set, then there is no loop in the linked list.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
// Function to detect and remove loop
// in a linked list
void hashAndRemove(Node* head)
{
// hash set to hash addresses of the linked list nodes
unordered_set<Node*> node_set;
// pointer to prev node
Node* prev = NULL;
while (head != NULL) {
// if node not present in the map, insert it in the
// map
if (node_set.find(head) == node_set.end()) {
node_set.insert(head);
prev = head;
head = head->next;
}
// if present, it is a cycle, make the last node's
// next pointer NULL
else {
prev->next = NULL;
break;
}
}
}
/* Driver program to test above function*/
int main()
{
Node* head = new Node(50);
head->next = new Node(20);
head->next->next = new Node(15);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(10);
/* Create a loop for testing */
head->next->next->next->next->next = head->next->next;
// printList(head);
hashAndRemove(head);
printf("Linked List after removing loop \n");
printList(head);
return 0;
}
import java.util.*;
public class LinkedList {
static Node head; // head of list
/* Linked list Node*/
static class Node {
int data;
Node next;
Node(int x)
{
data = x;
next = null;
}
}
// Function to print the linked list
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
// funtion to detect and remove loop from linked list
static void removeLoop(Node head)
{
HashSet<Node> s = new HashSet<Node>();
Node prev = null;
while (head != null) {
// If we have already has this node
// in hashmap it means there is a cycle and we
// need to remove this cycle so set the next of
// the previous pointer with null.
if (s.contains(head)) {
prev.next = null;
return;
}
// If we are seeing the node for
// the first time, insert it in hash
else {
s.add(head);
prev = head;
head = head.next;
}
}
}
/* Driver program to test above function */
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.head = new Node(50);
llist.head.next = new Node(20);
llist.head.next.next = new Node(15);
llist.head.next.next.next = new Node(4);
llist.head.next.next.next.next = new Node(10);
/*Create loop for testing */
llist.head.next.next.next.next.next
= llist.head.next.next;
removeLoop(llist.head);
System.out.println(
"Linked List after removing loop");
llist.printList(llist.head);
}
}
class Node:
def __init__(self, x):
self.data = x
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def print_list(self, node):
# Function to print the linked list
while node:
print(node.data, end=' ')
node = node.next
print()
@staticmethod
def remove_loop(head):
# Function to detect and remove loop from linked list
s = set()
prev = None
while head:
# If node is already in the set, remove the loop
if head in s:
prev.next = None
return
# Add node to the set and move forward
s.add(head)
prev = head
head = head.next
# Driver code
if __name__ == "__main__":
llist = LinkedList()
llist.head = Node(50)
llist.head.next = Node(20)
llist.head.next.next = Node(15)
llist.head.next.next.next = Node(4)
llist.head.next.next.next.next = Node(10)
# Create a loop for testing
llist.head.next.next.next.next.next = llist.head.next.next
LinkedList.remove_loop(llist.head)
print("Linked List after removing loop:")
llist.print_list(llist.head)
// C# program to detect and remove loop in a linked list
using System;
using System.Collections.Generic;
public class LinkedList {
public Node head; // head of list
/* Linked list Node*/
public class Node {
public int data;
public Node next;
public Node(int x)
{
data = x;
next = null;
}
}
// Function to print the linked list
void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
// function to detect and remove loop in linked list
void removeLoop(Node head)
{
HashSet<Node> s = new HashSet<Node>();
Node prev = null;
while (head != null) {
// If we have already has this node
// in hashmap it means there is a cycle and we
// need to remove this cycle so set the next of
// the previous pointer with null.
if (s.Contains(head)) {
prev.next = null;
return;
}
// If we are seeing the node for
// the first time, insert it in hash
else {
s.Add(head);
prev = head;
head = head.next;
}
}
}
/* Driver program to test above function */
public static void Main()
{
LinkedList list = new LinkedList();
list.head = new Node(50);
list.head.next = new Node(20);
list.head.next.next = new Node(15);
list.head.next.next.next = new Node(4);
list.head.next.next.next.next = new Node(10);
/*Create loop for testing */
list.head.next.next.next.next.next
= list.head.next.next;
list.removeLoop(list.head);
Console.WriteLine("Linked List after removing loop");
list.printList(list.head);
}
}
<script>
// javascript program to detect and remove loop in a linked list class LinkedList {
/* Linked list Node */
class Node {
constructor(x) {
this.data = x;
this.next = null;
}
}
var head; // head of list
// Function to print the linked list
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
// Returns true if the loop is removed from the linked
// list else returns false.
function removeLoop(head)
{
var s = new Set();
var prev = null;
while (head != null)
{
// If we have already has this node
// in hashmap it means there is a cycle and we
// need to remove this cycle so set the next of
// the previous pointer with null.
if (s.has(head)) {
prev.next = null;
return ;
}
// If we are seeing the node for
// the first time, insert it in hash
else {
s.add(head);
prev = head;
head = head.next;
}
}
}
/* Driver program to test above function */
head = new Node(50);
head.next = new Node(20);
head.next.next = new Node(15);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(10);
/* Create loop for testing */
head.next.next.next.next.next = head.next.next;
removeLoop(head);
document.write("Linked List after removing loop<br/>");
printList(head);
// This code is contributed by gauravrajput1
</script>
Output
Linked List after removing loop 50 20 15 4 10
Time Complexity: O(N), Where N is the number of nodes in the linked list.
Auxiliary Space: O(N), Where N is the number of nodes in the linked list(due to hashing).
Detect and Remove Loop in Linked List
Given a linked list, the task is to check if there is a loop present in it and remove it.
Example:
Consider the below linked list where the node 5 links to node 3 forming a loop in the linked list. The task is to remove the loop in the linked list by updating the next pointer of node 5 point to NULL.
Table of Content
- Approach 1- Using Hashing – O(N) Time and O(N) Space
- Approach 2- Using Floyd’s Cycle Detection Algorithm – O(N) Time and O(1) Space
- Approach 3- Using Floyd’s Cycle Detection Algorithm (without counting nodes in loop) – O(N) Time and O(1) Space
Contact Us