Detect and Remove the loop in a linked list

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

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

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 this problem with the help of some examples.

If the linked list given to us is:

  • According to the problem statement, we need to find the loop in the linked list and remove it.
  • 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, the problem is clear. So let’s see how we can approach it.

Before moving to the approach section, try to think about how you can approach this problem. 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 solve this problem.
  • 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 solve this problem?

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

Approach 1 (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

#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;
}

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

Our next approach uses Floyd’s Cycle Detection algorithm.

Approach and Algorithm (Floyd’s Cycle Detection)

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


Code Implementation

#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 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 tried to explain the most efficient approach to detect and remove the loop in a linked list. If you want to practice more questions on linked lists feel free to solve them at Prepbytes (Linked Lists).

Previous post ConcurrentLinkedQueue in Java With Examples
Next post Deletion At Different Positions in A Circular Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *