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
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).
Approach 2- Using Floyd’s Cycle Detection Algorithm – O(N) Time and O(1) Space:
This approach can be divided into two parts:
1. Detect Loop in Linked List using Floyd’s Cycle Detection Algorithm:
- Use two pointers, slow and fast and initialize them with the head of the linked list.
- Move the fast pointer forward by two nodes and move the slow pointer forward by one node.
- If the slow and fast pointer points to the same node, loop is found.
- Else if the fast pointer reaches NULL or the last node, then no loop is found.
- Else repeat the above steps till we reach the end of the linked list or a loop is found.
2. Remove Loop in Linked List (if any):
- Initialize two pointers, ptr1 and ptr2 pointing to the same node where slow and fast pointer met.
- Count the number of nodes, say K in the loop my moving one of the pointers forward.
- Fix ptr1 to head and ptr2 to K nodes after head.
- Move both the pointers at the same speed and the node where they meet is the starting node of the loop.
- Find the last node of the loop by moving one of the pointers.
- Remove the loop by updating the next pointer of last node to NULL.
Below is the implementation of the above algorithm:
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
Node* next;
Node(int x) {
data = x;
next = NULL;
}
};
/* Function to remove loop. */
void removeLoop(Node*, Node*);
/* This function detects and removes loop in the list
If loop was there in the list then it returns 1,
otherwise returns 0 */
void detectAndRemoveLoop(Node* list)
{
Node *slow_p = list, *fast_p = list;
// Iterate and find if loop exists or not
while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;
/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p) {
removeLoop(slow_p, list);
return;
}
}
}
/* Function to remove loop.
loop_node --> Pointer to one of the loop nodes
head --> Pointer to the start node of the linked list */
void removeLoop(Node* loop_node, Node* head)
{
Node* ptr1 = loop_node;
Node* ptr2 = loop_node;
// Count the number of nodes in loop
unsigned int k = 1, i;
while (ptr1->next != ptr2) {
ptr1 = ptr1->next;
k++;
}
// Fix one pointer to head
ptr1 = head;
// And the other pointer to k nodes after head
ptr2 = head;
for (i = 0; i < k; i++)
ptr2 = ptr2->next;
/* Move both pointers at the same pace,
they will meet at loop starting node */
while (ptr2 != ptr1) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
// Get pointer to the last node
while (ptr2->next != ptr1)
ptr2 = ptr2->next;
/* Set the next node of the loop ending node
to fix the loop */
ptr2->next = NULL;
}
/* Function to print linked list */
void printList(Node* node)
{
// Print the list after loop removal
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
// Driver Code
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;
detectAndRemoveLoop(head);
cout << "Linked List after removing loop \n";
printList(head);
return 0;
}
// Java program to detect and remove loop in linked list
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int x)
{
data = x;
next = null;
}
}
// Function that detects loop in the list
void detectAndRemoveLoop(Node node)
{
Node slow = node, fast = node;
while (slow != null && fast != null
&& fast.next != null) {
slow = slow.next;
fast = fast.next.next;
// If slow and fast meet at same point then loop
// is present
if (slow == fast) {
removeLoop(slow, node);
return;
}
}
}
// Function to remove loop
void removeLoop(Node loop, Node head)
{
Node ptr1 = loop;
Node ptr2 = loop;
// Count the number of nodes in loop
int k = 1, i;
Node prevNode = ptr1;
while (ptr1.next != ptr2) {
// keeping track beforeing moving next
prevNode = ptr1;
ptr1 = ptr1.next;
k++;
}
prevNode.next = null;
}
// Function to print the linked list
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
// Driver program to test above functions
public static void main(String[] args)
{
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);
// Creating a loop for testing
head.next.next.next.next.next = head.next.next;
list.detectAndRemoveLoop(head);
System.out.println(
"Linked List after removing loop : ");
list.printList(head);
}
}
// This code has been contributed by Mayank Jaiswal
# Python program to detect and remove loop in linked list
# Node class
class Node:
# Constructor to initialize the node object
def __init__(self, x):
self.data = x
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
def detectAndRemoveLoop(self):
slow_p = fast_p = self.head
while(slow_p and fast_p and fast_p.next):
slow_p = slow_p.next
fast_p = fast_p.next.next
# If slow_p and fast_p meet at some point then
# there is a loop
if slow_p == fast_p:
self.removeLoop(slow_p)
return
# Function to remove loop
# loop_node --> pointer to one of the loop nodes
# head --> Pointer to the start node of the linked list
def removeLoop(self, loop_node):
ptr1 = loop_node
ptr2 = loop_node
# Count the number of nodes in loop
k = 1
while(ptr1.next != ptr2):
ptr1 = ptr1.next
k += 1
# Fix one pointer to head
ptr1 = self.head
# And the other pointer to k nodes after head
ptr2 = self.head
for i in range(k):
ptr2 = ptr2.next
# Move both pointers at the same place
# they will meet at loop starting node
while(ptr2 != ptr1):
ptr1 = ptr1.next
ptr2 = ptr2.next
# Get pointer to the last node
while(ptr2.next != ptr1):
ptr2 = ptr2.next
# Set the next node of the loop ending node
# to fix the loop
ptr2.next = None
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Utility function to print the LinkedList
def printList(self):
temp = self.head
while(temp):
print(temp.data, end = ' ')
temp = temp.next
# Driver program
llist = LinkedList()
llist.push(10)
llist.push(4)
llist.push(15)
llist.push(20)
llist.push(50)
# Create a loop for testing
llist.head.next.next.next.next.next = llist.head.next.next
llist.detectAndRemoveLoop()
print("Linked List after removing loop")
llist.printList()
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
// A C# program to detect and remove loop in linked list
using System;
public class LinkedList {
Node head;
public class Node {
public int data;
public Node next;
public Node(int x)
{
data = x;
next = null;
}
}
// Function that detects loop in the list
void detectAndRemoveLoop(Node node)
{
Node slow = node, fast = node;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
// If slow and fast meet at same
// point then loop is present
if (slow == fast) {
removeLoop(slow, node);
return ;
}
}
}
// Function to remove loop
void removeLoop(Node loop, Node head)
{
Node ptr1 = loop;
Node ptr2 = loop;
// Count the number of nodes in loop
int k = 1, i;
while (ptr1.next != ptr2) {
ptr1 = ptr1.next;
k++;
}
// Fix one pointer to head
ptr1 = head;
// And the other pointer to k nodes after head
ptr2 = head;
for (i = 0; i < k; i++) {
ptr2 = ptr2.next;
}
/* Move both pointers at the same pace,
they will meet at loop starting node */
while (ptr2 != ptr1) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
// Get pointer to the last node
while (ptr2.next != ptr1) {
ptr2 = ptr2.next;
}
/* Set the next node of the loop ending node
to fix the loop */
ptr2.next = null;
}
// Function to print the linked list
void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
// Driver program to test above functions
public static void Main(String[] args)
{
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);
// Creating a loop for testing
list.head.next.next.next.next.next = list.head.next.next;
list.detectAndRemoveLoop(list.head);
Console.WriteLine("Linked List after removing loop : ");
list.printList(list.head);
}
}
// This code contributed by Rajput-Ji
<script>
// Javascript program to detect and
// remove loop in linked list
var head;
class Node
{
constructor(x)
{
this.data = x;
this.next = null;
}
}
// Function that detects loop in the list
function detectAndRemoveLoop(node)
{
var slow = node, fast = node;
while (slow != null &&
fast != null &&
fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
// If slow and fast meet at same
// point then loop is present
if (slow == fast)
{
removeLoop(slow, node);
return ;
}
}
}
// Function to remove loop
function removeLoop(loop, head)
{
var ptr1 = loop;
var ptr2 = loop;
// Count the number of nodes in loop
var k = 1, i;
while (ptr1.next != ptr2)
{
ptr1 = ptr1.next;
k++;
}
// Fix one pointer to head
ptr1 = head;
// And the other pointer to
// k nodes after head
ptr2 = head;
for(i = 0; i < k; i++)
{
ptr2 = ptr2.next;
}
/* Move both pointers at the same pace,
they will meet at loop starting node */
while (ptr2 != ptr1)
{
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
// Get pointer to the last node
while (ptr2.next != ptr1)
{
ptr2 = ptr2.next;
}
/* Set the next node of the loop ending node
to fix the loop */
ptr2.next = null;
}
// Function to print the linked list
function printList(node)
{
while (node != null)
{
document.write(node.data + " ");
node = node.next;
}
}
// Driver code
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);
// Creating a loop for testing
head.next.next.next.next.next = head.next.next;
detectAndRemoveLoop(head);
document.write("Linked List after removing loop : ");
printList(head);
// This code is contributed by todaysgaurav
</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 tree
Auxiliary Space: O(1)
Approach 3- Using Floyd’s Cycle Detection Algorithm (without counting nodes in loop) – O(N) Time and O(1) Space
We do not need to count the number of nodes in Loop. After detecting the loop, if we start the slow pointer from the head and move both slow and fast pointers at the same speed until fast don’t meet, they would meet at the beginning of the loop.
How does this work?
Let slow and fast meet at some point after Floyd’s Cycle finding algorithm. The below diagram shows the situation when the cycle is found.
We can conclude below from the above diagram
Distance traveled by fast pointer = 2 * (Distance traveled by slow pointer)
(m + n*x + k) = 2*(m + n*y + k)
Note that before meeting the point shown above, fast was moving at twice speed.
x = Number of complete cyclic rounds made by fast pointer before they meet first time y = Number of complete cyclic rounds made by slow pointer before they meet first time
From the above equation, we can conclude below
m + k = (x-2y)*n, which means m+k is a multiple of n. Thus we can write, m + k = i*n or m = i*n – k. Hence, distance moved by slow pointer: m, is equal to distance moved by fast pointer: i*n – k or (i-1)*n + n – k (cover the loop completely i-1 times and start from n-k).
So, if we start moving both pointers again at same speed such that one pointer (say slow) begins from head node of linked list and other pointer (say fast) begins from meeting point. When the slow pointer reaches the beginning of the loop (has made m steps), the fast pointer would have made also moved m steps as they are now moving at the same pace. Since m+k is a multiple of n and fast starts from k, they would meet at the beginning. Can they meet before also? No because slow pointer enters the cycle first time after m steps.
Below is the implementation of the algorithm:
// C++ program to detect and remove loop
#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 that
// may contain loop
void detectAndRemoveLoop(Node* head)
{
// If list is empty or has only one node without loop
if (head == NULL || head->next == NULL)
return;
Node *slow = head, *fast = head;
// Move slow and fast 1 and 2 steps ahead respectively.
slow = slow->next;
fast = fast->next->next;
// Search for loop using slow and fast pointers
while (fast && fast->next) {
if (slow == fast)
break;
slow = slow->next;
fast = fast->next->next;
}
/* If loop exists */
if (slow == fast) {
slow = head;
// this check is needed when slow and fast both meet
// at the head of the LL eg: 1->2->3->4->5 and then
// 5->next = 1 i.e the head of the LL
if (slow == fast)
while (fast->next != slow)
fast = fast->next;
else {
while (slow->next != fast->next) {
slow = slow->next;
fast = fast->next;
}
}
/* since fast->next is the looping point */
fast->next = NULL; /* remove loop */
}
}
/* 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;
detectAndRemoveLoop(head);
printf("Linked List after removing loop \n");
printList(head);
return 0;
}
// C++ program to detect and remove loop
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
struct Node* next;
} Node;
Node* newNode(int key)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->key = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
printf("%d ", head->key);
head = head->next;
}
printf("\n");
}
// Function to detect and remove loop in a linked list that
// may contain loop
void detectAndRemoveLoop(Node* head)
{
// If list is empty or has only one node without loop
if (head == NULL || head->next == NULL)
return;
Node *slow = head, *fast = head;
// Move slow and fast 1 and 2 steps ahead respectively.
slow = slow->next;
fast = fast->next->next;
// Search for loop using slow and fast pointers
while (fast && fast->next) {
if (slow == fast)
break;
slow = slow->next;
fast = fast->next->next;
}
/* If loop exists */
if (slow == fast) {
slow = head;
// this check is needed when slow and fast both meet
// at the head of the LL eg: 1->2->3->4->5 and then
// 5->next = 1 i.e the head of the LL
if (slow == fast)
while (fast->next != slow)
fast = fast->next;
else {
while (slow->next != fast->next) {
slow = slow->next;
fast = fast->next;
}
}
/* since fast->next is the looping point */
fast->next = NULL; /* remove loop */
}
}
/* Driver program to test above function*/
int main()
{
Node* head = newNode(50);
head->next = head;
head->next = newNode(20);
head->next->next = newNode(15);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(10);
/* Create a loop for testing */
head->next->next->next->next->next = head;
detectAndRemoveLoop(head);
printf("Linked List after removing loop \n");
printList(head);
return 0;
}
// Java program to detect
// and remove loop in linked list
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int x)
{
data = x;
next = null;
}
}
// Function that detects loop in the list
void detectAndRemoveLoop(Node node)
{
// If list is empty or has only one node
// without loop
if (node == null || node.next == null)
return;
Node slow = node, fast = node;
// Move slow and fast 1 and 2 steps
// ahead respectively.
slow = slow.next;
fast = fast.next.next;
// Search for loop using slow and fast pointers
while (fast != null && fast.next != null) {
if (slow == fast)
break;
slow = slow.next;
fast = fast.next.next;
}
/* If loop exists */
if (slow == fast) {
slow = node;
if (slow != fast) {
while (slow.next != fast.next) {
slow = slow.next;
fast = fast.next;
}
/* since fast->next is the looping point */
fast.next = null; /* remove loop */
}
/* This case is added if fast and slow pointer meet at first position. */
else {
while(fast.next != slow) {
fast = fast.next;
}
fast.next = null;
}
}
}
// Function to print the linked list
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
// Driver code
public static void main(String[] args)
{
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);
// Creating a loop for testing
head.next.next.next.next.next = head.next.next;
list.detectAndRemoveLoop(head);
System.out.println("Linked List after removing loop : ");
list.printList(head);
}
}
# Python program to detect and remove loop
# Node class
class Node:
# Constructor to initialize the node object
def __init__(self, x):
self.data = x
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def detectAndRemoveLoop(self):
if self.head is None:
return
if self.head.next is None:
return
slow_p = self.head
fast_p = self.head
while(slow_p and fast_p and fast_p.next):
slow_p = slow_p.next
fast_p = fast_p.next.next
# If slow_p and fast_p meet at some point then
# there is a loop
if slow_p == fast_p:
slow_p = self.head
# Finding the beginning of the loop
while (slow_p.next != fast_p.next):
slow_p = slow_p.next
fast_p = fast_p.next
# Sinc fast.next is the looping point
fast_p.next = None # Remove loop
# Utility function to print the LinkedList
def printList(self):
temp = self.head
while(temp):
print(temp.data, end = ' ')
temp = temp.next
# Driver program
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
llist.detectAndRemoveLoop()
print("Linked List after removing loop")
llist.printList()
// C# program to detect and remove loop in linked list
using System;
public class LinkedList {
public Node head;
public class Node {
public int data;
public Node next;
public Node(int x)
{
data = x;
next = null;
}
}
// Function that detects loop in the list
void detectAndRemoveLoop(Node node)
{
// If list is empty or has only one node
// without loop
if (node == null || node.next == null)
return;
Node slow = node, fast = node;
// Move slow and fast 1 and 2 steps
// ahead respectively.
slow = slow.next;
fast = fast.next.next;
// Search for loop using slow and fast pointers
while (fast != null && fast.next != null) {
if (slow == fast)
break;
slow = slow.next;
fast = fast.next.next;
}
/* If loop exists */
if (slow == fast) {
slow = node;
while (slow.next != fast.next) {
slow = slow.next;
fast = fast.next;
}
/* since fast->next is the looping point */
fast.next = null; /* remove loop */
}
}
// Function to print the linked list
void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
// Driver program to test above functions
public static void Main(String[] args)
{
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);
// Creating a loop for testing
list.head.next.next.next.next.next = list.head.next.next;
list.detectAndRemoveLoop(list.head);
Console.WriteLine("Linked List after removing loop : ");
list.printList(list.head);
}
}
<script>
// javascript program to detect
// and remove loop in linked list
var head;
class Node
{
constructor(x)
{
this.data = x;
this.next = null;
}
}
// Function that detects loop in the list
function detectAndRemoveLoop(node) {
// If list is empty or has only one node
// without loop
if (node == null || node.next == null)
return;
var slow = node, fast = node;
// Move slow and fast 1 and 2 steps
// ahead respectively.
slow = slow.next;
fast = fast.next.next;
// Search for loop using slow and fast pointers
while (fast != null && fast.next != null) {
if (slow == fast)
break;
slow = slow.next;
fast = fast.next.next;
}
/* If loop exists */
if (slow == fast) {
slow = node;
if (slow != fast) {
while (slow.next != fast.next) {
slow = slow.next;
fast = fast.next;
}
/* since fast->next is the looping point */
fast.next = null; /* remove loop */
}
/* This case is added if fast and
slow pointer meet at first position. */
else {
while (fast.next != slow) {
fast = fast.next;
}
fast.next = null;
}
}
}
// Function to print the linked list
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
// Driver code
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);
// Creating a loop for testing
head.next.next.next.next.next = head.next.next;
detectAndRemoveLoop(head);
document.write("Linked List after removing loop : ");
printList(head);
</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 tree
Auxiliary Space: O(1)
Contact Us