Detect and remove loop in a linked list gfg practice

Detect and Remove Loop in a Linked List

Write a function detectAndRemoveLoop() that checks whether a given Linked List contains loop and if loop is present then removes the loop and returns true. If the list doesn’t contain loop then it returns false. Below diagram shows a linked list with a loop. detectAndRemoveLoop() must change the below list to 1->2->3->4->5->NULL.

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

We also recommend to read following post as a prerequisite of the solution discussed here.
Write a C function to detect loop in a linked list
Before trying to remove the loop, we must detect it. Techniques discussed in the above post can be used to detect loop. To remove loop, all we need to do is to get pointer to the last node of the loop. For example, node with value 5 in the above diagram. Once we have pointer to the last node, we can make the next of this node as NULL and loop is gone.
We can easily use Hashing or Visited node techniques (discussed in the above mentioned post) to get the pointer to the last node. Idea is simple: the very first node whose next is already visited (or hashed) is the last node.
We can also use Floyd Cycle Detection algorithm to detect and remove the loop. In the Floyd’s algo, the slow and fast pointers meet at a loop node. We can use this loop node to remove cycle. There are following two different ways of removing loop when Floyd’s algorithm is used for Loop detection.

Method 1 (Check one by one) We know that Floyd’s Cycle detection algorithm terminates when fast and slow pointers meet at a common point. We also know that this common point is one of the loop nodes (2 or 3 or 4 or 5 in the above diagram). Store the address of this in a pointer variable say ptr2. After that start from the head of the Linked List and check for nodes one by one if they are reachable from ptr2. Whenever we find a node that is reachable, we know that this node is the starting node of the loop in Linked List and we can get the pointer to the previous of this node.

Output:



Linked List after removing loop 50 20 15 4 10

Method 2 (Better Solution)

  1. This method is also dependent on Floyd’s Cycle detection algorithm.
  2. Detect Loop using Floyd’s Cycle detection algorithm and get the pointer to a loop node.
  3. Count the number of nodes in loop. Let the count be k.
  4. Fix one pointer to the head and another to a kth node from the head.
  5. Move both pointers at the same pace, they will meet at loop starting node.
  6. Get a pointer to the last node of the loop and make next of it as NULL.

Thanks to WgpShashank for suggesting this method.
Below image is a dry run of ‘remove loop’ function in the code :

Detect and remove loop in a linked list gfg practice

Below is the implementation of the above approach:




#include

using namespace std;

/* Link list node */

struct Node {

int data;

struct Node* next;

};

/* Function to remove loop. */

void removeLoop(struct Node*, struct Node*);

/* This function detects and removes loop in the list

If loop was there in the list then it returns 1,

otherwise returns 0 */

int detectAndRemoveLoop(struct Node* list)

{

struct 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 1 to indicate that loop is found */

return 1;

}

}

/* Return 0 to indicate that there is no loop*/

return 0;

}

/* 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(struct Node* loop_node, struct Node* head)

{

struct Node* ptr1 = loop_node;

struct 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(struct Node* node)

{

// Print the list after loop removal

while (node != NULL) {

cout << node->data << " ";

node = node->next;

}

}

struct Node* newNode(int key)

{

struct Node* temp = new Node();

temp->data = key;

temp->next = NULL;

return temp;

}

// Driver Code

int main()

{

struct Node* head = newNode(50);

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->next->next;

detectAndRemoveLoop(head);

cout << "Linked List after removing loop \n";

printList(head);

return 0;

}

// This code has been contributed by Striver




#include

using namespace std;

/* Link list node */

struct Node {

int data;

struct Node* next;

};

/* Function to remove loop. */

void removeLoop(struct Node*, struct Node*);

/* This function detects and removes loop in the list

If loop was there in the list then it returns 1,

otherwise returns 0 */

int detectAndRemoveLoop(struct Node* list)

{

struct 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 1 to indicate that loop is found */

return 1;

}

}

/* Return 0 to indicate that there is no loop*/

return 0;

}

/* 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(struct Node* loop_node, struct Node* head)

{

struct Node* ptr1 = loop_node;

struct 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(struct Node* node)

{

// Print the list after loop removal

while (node != NULL) {

cout << node->data << " ";

node = node->next;

}

}

struct Node* newNode(int key)

{

struct Node* temp = new Node();

temp->data = key;

temp->next = NULL;

return temp;

}

// Driver Code

int main()

{

struct Node* head = newNode(50);

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->next->next;

detectAndRemoveLoop(head);

cout << "Linked List after removing loop \n";

printList(head);

return 0;

}

// This code has been contributed by Striver




// Java program to detect and remove loop in linked list

class LinkedList {

static Node head;

static class Node {

int data;

Node next;

Node(int d)

{

data = d;

next = null;

}

}

// Function that detects loop in the list

int 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 1;

}

}

return 0;

}

// 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) {

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, data):

self.data = data

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 1 to indicate that loop is found

return 1

# Return 0 to indicate that there is no loop

return 0

# 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 d)

{

data = d;

next = null;

}

}

// Function that detects loop in the list

int 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 1;

}

}

return 0;

}

// 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




Output:

Linked List after removing loop 50 20 15 4 10

Method 3 (Optimized Method 2: Without Counting Nodes in Loop)
We do not need to count number of nodes in Loop. After detecting the loop, if we start slow pointer from head and move both slow and fast pointers at 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. Below diagram shows the situation when cycle is found.

Detect and remove loop in a linked list gfg practice

We can conclude below from 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 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 slow pointer reaches beginning of loop (has made m steps), fast pointer would have made also moved m steps as they are now moving 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.




// C++ program to detect and remove loop

#include

using namespace std;

struct Node {

int key;

struct Node* next;

};

Node* newNode(int key)

{

Node* temp = new Node;

temp->key = key;

temp->next = NULL;

return temp;

}

// A utility function to print a linked list

void printList(Node* head)

{

while (head != NULL) {

cout << head->key << " ";

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 = 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 d)

{

data = d;

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);

}

}

// This code has been contributed by Mayank Jaiswal




# Python program to detect and remove loop

# Node class

class Node:

# Constructor to initialize the node object

def __init__(self, data):

self.data = data

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()

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)




// 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 d)

{

data = d;

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);

}

}

// This code contributed by Rajput-Ji




Output:

Linked List after removing loop 50 20 15 4 10

Method 4 Hashing: Hash the address of the linked list nodes
We can hash the addresses of the linked list nodes in an unordered map and just check if the element already exists in the map. If it exists, we have reached a node which already exists by a cycle, hence we need to make the last node’s next pointer NULL.




// C++ program to detect and remove loop

#include

using namespace std;

struct Node {

int key;

struct Node* next;

};

Node* newNode(int key)

{

Node* temp = new Node;

temp->key = key;

temp->next = NULL;

return temp;

}

// A utility function to print a linked list

void printList(Node* head)

{

while (head != NULL) {

cout << head->key << " ";

head = head->next;

}

cout << endl;

}

// Function to detect and remove loop

// in a linked list that may contain loop

void hashAndRemove(Node* head)

{

// hash map to hash addresses of the linked list nodes

unordered_map node_map;

// pointer to last node

Node* last = NULL;

while (head != NULL) {

// if node not present in the map, insert it in the map

if (node_map.find(head) == node_map.end()) {

node_map[head]++;

last = head;

head = head->next;

}

// if present, it is a cycle, make the last node's next pointer NULL

else {

last->next = NULL;

break;

}

}

}

/* 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->next->next;

// printList(head);

hashAndRemove(head);

printf("Linked List after removing loop \n");

printList(head);

return 0;

}




// Java program to detect and remove loop in a linked list

import java.util.*;

public class LinkedList {

static Node head; // head of list

/* Linked list Node*/

static class Node {

int data;

Node next;

Node(int d)

{

data = d;

next = null;

}

}

/* Inserts a new Node at front of the list. */

static public void push(int new_data)

{

/* 1 & 2: Allocate the Node &

Put in the data*/

Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

new_node.next = head;

/* 4. Move the head to point to new Node */

head = new_node;

}

// Function to print the linked list

void printList(Node node)

{

while (node != null) {

System.out.print(node.data + " ");

node = node.next;

}

}

// Returns true if the loop is removed from the linked

// list else returns false.

static boolean removeLoop(Node h)

{

HashSet s = new HashSet();

Node prev = null;

while (h != null) {

// If we have already has this node

// in hashmap it means their is a cycle and we

// need to remove this cycle so set the next of

// the previous pointer with null.

if (s.contains(h)) {

prev.next = null;

return true;

}

// If we are seeing the node for

// the first time, insert it in hash

else {

s.add(h);

prev = h;

h = h.next;

}

}

return false;

}

/* Driver program to test above function */

public static void main(String[] args)

{

LinkedList llist = new LinkedList();

llist.push(20);

llist.push(4);

llist.push(15);

llist.push(10);

/*Create loop for testing */

llist.head.next.next.next.next = llist.head;

if (removeLoop(head)) {

System.out.println("Linked List after removing loop");

llist.printList(head);

}

else

System.out.println("No Loop found");

}

}

// This code is contributed by Animesh Nag.




// 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 d)

{

data = d;

next = null;

}

}

// Function to print the linked list

void printList(Node node)

{

while (node != null) {

Console.Write(node.data + " ");

node = node.next;

}

}

// Returns true if the loop is removed from the linked

// list else returns false.

bool removeLoop(Node h)

{

HashSet s = new HashSet();

Node prev = null;

while (h != null) {

// If we have already has this node

// in hashmap it means their is a cycle and we

// need to remove this cycle so set the next of

// the previous pointer with null.

if (s.Contains(h)) {

prev.next = null;

return true;

}

// If we are seeing the node for

// the first time, insert it in hash

else {

s.Add(h);

prev = h;

h = h.next;

}

}

return false;

}

/* 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;

if (list.removeLoop(list.head)) {

Console.WriteLine("Linked List after removing loop");

list.printList(list.head);

}

else

Console.WriteLine("No Loop found");

}

}

// This code is contributed by ihritik




Output Linked List after removing loop 50 20 15 4 10

We Thank Shubham Agrawal for suggesting this solution.

Thanks to Gaurav Ahirwar for suggesting the above solution.
Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.

Detect and remove loop in a linked list gfg practice




Article Tags :

Linked List

Amazon

MakeMyTrip

Microsoft

Morgan Stanley

Oracle

Samsung

Snapdeal

Tortoise-Hare-Approach

VMWare

Walmart

Practice Tags :

VMWare

Morgan Stanley

Amazon

Microsoft

Samsung

Snapdeal

MakeMyTrip

Oracle

Walmart

Linked List

1. Using Hashing

A simple solution is to use hashing. The idea is to traverse the given linked list and insert each encountered node into a hash set. If the node is already present in the HashSet, that means it is seen before and points to the first node in the cycle. To break the cycle, set the next pointer of the previous node to null.

Following is the implementation of the above idea in C++, Java, and Python. The code uses two pointers: curr and prev, where curr is the main pointer running down the list, and prev trails it.

C++


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

#include

#include

using namespace std;

// A Linked List Node

struct Node

{

int data;

Node* next;

};

// Utility function to create a new node with the given data and

// pushes it onto the list's front

void push(Node*& headRef, int data)

{

// create a new linked list node from the heap

Node* newNode = new Node;

newNode->data = data;

newNode->next = headRef;

headRef = newNode;

}

// Utility function to print a linked list

void printList(Node* head)

{

Node* curr = head;

while (curr)

{

cout << curr->data << " —> ";

curr = curr->next;

}

cout << "nullptr";

}

// Function to identify and remove cycle in a linked list using hashing

void removeCycle(Node* head)

{

Node* prev = nullptr; // previous pointer

Node* curr = head;// main pointer

// maintain a set to store visited nodes

unordered_set<Node*> set;

// traverse the list

while (curr)

{

// set the previous pointer to null if the current node is seen before

if (set.find(curr) != set.end())

{

prev->next = nullptr;

return;

}

// insert the current node into the set

set.insert(curr);

// update the previous pointer to the current node and

// move the main pointer to the next node

prev = curr;

curr = curr->next;

}

}

int main()

{

// total number of nodes in the linked list

int n = 5;

// construct a linked list

Node* head = nullptr;

for (int i = n; i > 0; i--) {

push(head, i);

}

// insert cycle

head->next->next->next->next->next = head->next;

removeCycle(head);

printList(head);

return 0;

}

DownloadRun Code

Output:

1 —> 2 —> 3 —> 4 —> 5 —> nullptr