Detect and Remove the loop in a linked list

Last Updated on November 10, 2022 by Prepbytes

In this article, we will learn to detect and remove loop in a linked list. A loop is a linked list defined as a condition that when the last node of the linked list doesn’t point to the NULL.let’s now try to understand the detection and removal of a loop in linked list.

Problem Statement

In this problem, we are given a singly linked list, which may contain a loop. We have to detect the loop, and if there is a loop, we need to remove it from the linked list.

Problem Statement Understanding to remove loop in linked list

The linked list contains a loop means the last node in the list will not be pointing to the NULL instead, it will be pointing to some other node in the list.

Removing the loop means that the we need to make the last node of the list point to NULL instead of pointing to some other node in the list.

Let’s understand how we can detect and remove loop in a linked list with the help of some examples.

If the linked list given to us is:

• According to the problem statement, we need to detect and remove loop in a linked list.
• From the linked list, we can see that there is a loop in the linked list starting at the node with value 0 and containing 4 nodes 0, 3, 0, and 1. The last node of the loop points back to the first node of the loop.
• Now, as we found out that there is a loop in the given linked list, so now we have to remove the loop from the linked list.
• So, the final linked list after removing the loop loop will be 1 – > 0 – > 3 – > 0 – > 1 -> NULL

Now I think from the above examples detection and removal of a loop in linked list is clear. So let’s see how we can approach to remove loop in linked list

Before moving to the approach section, try to think about how you can detect and remove loop in a linked list. What is the first thing that comes to your mind?

• The very first thing that comes to mind is loop detection. Correct, but we can also use hashing to remove loop in linked list,.

• The hashing solution will require O(n) space for the creation of the hash table, so we are first going to look at hashing approach, and then jump to the efficient loop detection approach using Floyd’s Cycle Detection Algorithm.

Try to think about how you can use hashing to detect and remove loop in a linked list ?

Let us have a glance at the approach to get a clear look.

Approach 1 to remove loop in linked list (Hashing)

This approach is going to be pretty simple.

• We are going to use an unordered_map and we will keep inserting nodes into it while traversing the linked list.
• Now, Once we encounter a node that is already present in the map, it will mean that we have reached the starting point of the loop.
  • Also, while iterating, we were maintaining two pointers at each step head and last, head pointing to the current node and last to the previous node of the current node.
  • As now our head is pointing to the start node of the loop and as last was pointing to the previous node of the node to which head was pointing, i.e., it is pointing to the last node of the loop.
  • So, now we will break the loop by making last->next == NULL.
• In this way, the last loop node starts pointing to NULL instead of pointing to the starting node of the loop.

Code Implementation to detect and remove loop in a linked list

#include 
using namespace std;
 
/* Node structure of the linked list node */
struct Node {
    int key;
    struct Node* next;
};
 
/* Using this function we will be creating a new node of the linked list */
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->next = NULL;
    return temp;
}

/* Using this function we will be printing the content of the linked list */
void printList(Node* head)
{
    while (head != NULL) {
        cout << head->key << " ";
        head = head->next;
    }
    cout << endl;
}

/* Using this function we will be detecting and removing loop from the linked list */
void hashAndRemove(Node* head)
{
    
    unordered_map node_map;

    Node* last = NULL;
    while (head != NULL) {
       
        if (node_map.find(head) == node_map.end()) {
            node_map[head]++;
            last = head;
            head = head->next;
        }
        
        else {
            last->next = NULL;
            break;
        }
    }
}

int main()
{
    Node* head = newNode(1);
    head->next = head;
    head->next = newNode(0);
    head->next->next = newNode(3);
    head->next->next->next = newNode(0);
    head->next->next->next->next = newNode(1);
 
    head->next->next->next->next->next = head->next;

    hashAndRemove(head);
 
    printf("Linked List after removing loop : \n");
    printList(head);
 
    return 0;
}

import java.util.*;
class DetectLoop {

	static Node head;

	static class Node {
		int data;
		Node next;
		Node(int d)
		{
			data = d;
			next = null;
		}
	}
	static public void push(int new_data)
	{

		Node new_node = new Node(new_data);

		new_node.next = head;

		head = new_node;
	}
	void printList(Node node)
	{
		while (node != null) {
			System.out.print(node.data + " ");
			node = node.next;
		}
	}
	static boolean removeLoop(Node h)
	{
		HashSet s = new HashSet();
		Node prev = null;
		while (h != null) {
			if (s.contains(h)) {
				prev.next = null;
				return true;
			}
			else {
				s.add(h);
				prev = h;
				h = h.next;
			}
		}

		return false;
	}

	/* Driver program to test above function */
	public static void main(String[] args)
	{
		DetectLoop llist = new DetectLoop();

		llist.push(20);
		llist.push(4);
		llist.push(15);
		llist.push(10);

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

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
def printList(head):
    curr = head
    while curr:
        print(curr.data, end=' —> ')
        curr = curr.next
    print('None')
 
 
def removeCycle(head):
    prev = None        
    curr = head        
    s = set()
    while curr:
        if curr in s:
            prev.next = None
            return

        s.add(curr)
        prev = curr
        curr = curr.next
 
if __name__ == '__main__':
 
    head = None
    head = Node(1, head)
    head = Node(0, head)
    head = Node(3, head)
    head = Node(0, head)
    head = Node(1, head)
 
    head.next.next.next.next.next = head.next
 
    removeCycle(head)
    printList(head)

Output

Linked List after removing loop
1 0 3 0 1

Time Complexity – O(n), as list traversal is needed.
Space Complexity – O(n), the space required by the map.

This approach to remove loop in linked list will work fine, but it requires extra O(n) space. So, now the main question is can we optimize this space?

• The answer is yes, and we will see how we can optimize this space in the next approach for detection and removal of a loop in linked list.

Our next approach uses Floyd’s Cycle Detection algorithm to remove loop in linked list.

Approach and Algorithm (Floyd’s Cycle Detection) to detect and remove loop in a linked list

In this approach, we are going to use Floyd’s Cycle Detection algorithm.

1. Firstly, we have to detect the loop in the given linked list.
• We know the most efficient algorithm for detecting a loop in any linked list is the Floyd Cycle detection Algorithm.
2. In Floyd’s cycle detection algorithm, we initialize 2 pointers, slow and fast.
• Both initially point to the head of the list.
• The slow pointer jumps one place and the fast pointer jumps 2 places.
• If, at any point, slow and fast meet, it means that there exists a loop in the list. The point where slow and fast meet is somewhere inside the loop.
3. Now, after detecting the loop, we will make slow point to the head and fast will be at its position only (Inside the loop).
• If still slow == fast, it means that the slow and fast met at the head node of the linked list.
  • So, in this case, we will run a while loop until fast->next != slow (inside loop move fast by one node at a time) and when fast->next == slow, we will remove the loop by making fast->next == NULL.
• Now, if slow != fast, in this case, we will run a while loop until slow -> next is not equal to fast -> next (inside while loop move both slow and fast forward by 1 node), and when slow->next == fast->next, it means that fast is pointing to the last node of the loop, so we will remove the loop by making fast->next == NULL.
  4) In this way, if there is any loop in the linked list, it will get removed.

Dry run to detect and remove loop in a linked list

Code Implementation to detect and remove loop in a linked list

#include<stdio.h>
#include<stdlib.h>

struct Node {
    int data;
    struct Node* next;
};
 
void removeLoop(struct Node*, struct Node*);
 
int detectAndRemoveLoop(struct Node* list)
{
    struct Node *slow_p = list, *fast_p = list;
 
    while (slow_p && fast_p && fast_p->next) {
        slow_p = slow_p->next;
        fast_p = fast_p->next->next;
 
        if (slow_p == fast_p) {
            removeLoop(slow_p, list);
 
            return 1;
        }
    }
 
    return 0;
}
 
void removeLoop(struct Node* loop_node, struct Node* head)
{
    struct Node* ptr1 = loop_node;
    struct Node* ptr2 = loop_node;
 
    unsigned int k = 1, i;
    while (ptr1->next != ptr2) {
        ptr1 = ptr1->next;
        k++;
    }
    ptr1 = head;
 
    ptr2 = head;
    for (i = 0; i < k; i++)
        ptr2 = ptr2->next;
 
    while (ptr2 != ptr1) {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
 
    while (ptr2->next != ptr1)
        ptr2 = ptr2->next;
 
    ptr2->next = NULL;
	
}
void printList(struct Node* node)
{
    // Print the list after loop removal
    while (node != NULL) {
        printf("%d ",node->data);
        node = node->next;
    }
}
 
struct Node* newNode(int x)
{
    struct Node* node = malloc(sizeof(struct Node*));
    node->data = x;
    node->next = NULL;
    return node;
}
 
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);
 
    head->next->next->next->next->next = head->next->next;
 
    detectAndRemoveLoop(head);
 
    printf("Linked List after removing loop \n");
    printList(head);
    return 0;
}

#include <bits stdc++.h>
using namespace std;
 
/* Node structure of the linked list node */
struct Node {
    int key;
    struct Node* next;
};

/* Using this function we will be creating a new node of the linked list */
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->next = NULL;
    return temp;
}

/* Using this function we will be printing the content of the linked list */
void printList(Node* head)
{
    while (head != NULL) {
        cout << head->key << " ";
        head = head->next;
    }
    cout << endl;
}

/* Using this function we will be detecting and removing loop from the linked list */
void detectAndRemoveLoop(Node* head)
{

    if (head == NULL || head->next == NULL)
        return;
 
    Node *slow = head, *fast = head;

    slow = slow->next;
    fast = fast->next->next;

    while (fast && fast->next) {
        if (slow == fast)
            break;
        slow = slow->next;
        fast = fast->next->next;
    }
 
    /* If loop exists */
    if (slow == fast)
    {
        slow = head;

          if(slow == fast) {
              while(fast->next != slow) fast = fast->next;
        }
          else {
            while (slow->next != fast->next) {
                slow = slow->next;
                fast = fast->next;
            }
        }
 
        fast->next = NULL; 
    }
}

int main()
{
    Node* head = newNode(1);
    head->next = head;
    head->next = newNode(0);
    head->next->next = newNode(3);
    head->next->next->next = newNode(0);
    head->next->next->next->next = newNode(1);

    head->next->next->next->next->next = head->next;
 
    detectAndRemoveLoop(head);
 
    printf("Linked List after removing loop : \n");
    printList(head);
 
    return 0;
}

public class LinkedList {

    static Node head;
    
    /* Node structure of the linked list node */
    static class Node {

        int data;
        Node next;

        Node(int d)
        {
            data = d;
            next = null;
        }
    }
    
    /* Using this function we will be detecting and removing loop from the linked list */
    void detectAndRemoveLoop(Node node)
    {

        if (node == null || node.next == null)
            return;

        Node slow = node, fast = node;

        slow = slow.next;
        fast = fast.next.next;

        while (fast != null && fast.next != null) {
            if (slow == fast)
                break;

            slow = slow.next;
            fast = fast.next.next;
        }

        if (slow == fast) {
            slow = node;
            if (slow != fast) {
                while (slow.next != fast.next) {
                    slow = slow.next;
                    fast = fast.next;
                }

                fast.next = null; 
            }

            else {
                while(fast.next != slow) {
                    fast = fast.next;
                }
                fast.next = null;
            }
        }
    }
    
    /* Using this function we will be printing the content of the linked list */
    void printList(Node node)
    {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        list.head.next = new Node(0);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(0);
        list.head.next.next.next.next = new Node(1);

        head.next.next.next.next.next = head.next;
        list.detectAndRemoveLoop(head);
        System.out.println("Linked List after removing loop : ");
        list.printList(head);
    }
}

Output:
Linked List after removing loop :
1 0 3 0 1

Time Complexity: O(n), as list traversal is needed.

So, in this article, we have explained how to detect and remove the loop in a linked list. We have explained both approaches i.e.hashing and Floyd’s Cycle Detection algorithm with picturised dry run and code implementation as well.This is one of the most important question asked in interviews .If you want to practice more questions on linked lists feel free to solve them at Prepbytes (Linked Lists).

FAQs to remove loop in linked list

1. Explain the type of memory allocation in linked list?


Dynamic memory allocation is used to allocate memory in linked lists.


2. Can we access the random element of the linked list?


We can not access any node directly, if we want to access any node then we have the traverse the linked list.


3. Is it possible to find a loop in linked list time complexity?


Basically complexity is not counted by the number of loop steps,but the nodes visite