Data Structures and Algorithms — Linked Lists #2 — Remove loop in a Linked List

Problem statement:

Given a linked list of N nodes such that it may contain a loop.

A loop here means that the last node of the link list is connected to the node at position X.

Remove the loop from the linked list, if it is present.

Example :

Input:
N = 3
value[] = {1,3,4}

Output: 1
Explanation: The linked list looks like
1 -> 3 -> 4
     ^    |
     |____|    
A loop is present. 

Simply remove the loop in the list (if present) without disconnecting any nodes from the list.

Expected time complexity: O(N)
Expected auxiliary space: O(1)

Asked in following companies:

Adobe, Amazon, Goldman Sachs, MakeMyTrip, Microsoft ,Morgan Stanley, Oracle, Snapdeal, VMWare,Walmart

Brute force approach:

The key idea is to detect if the loop is present or not, if it is present we need to break the loop.

A. Using hashing

1. Traverse the Linked list, by maintaining 2 pointers — current & previous.
2. Use a HashSet to keep track of the nodes.
3. If the current node does not exist in the set, we will add it.
4. If the current node exists in the set, it means we have detected a loop.
5. Set the next pointer of the previous node to NULL, thus the cycle breaks.

Complexity Analysis:

Time Complexity: O(n).
n is the total number of nodes in the linked list.

Auxiliary Space: O(n).
Use of additional Set data structure.

B. Optimal Solution — Using Floyd’s Cycle Detection Algorithm

In this solution, we will use this algorithm and with the help of that we will learn how to solve 3 types of questions:

1. Detect a loop in linked list.
2. Find the length of loop in the linked list.
3. Remove loop in the linked list.

What is Floyd’s Cycle detection algorithm?

Floyd’s cycle detection algorithm maintains two pointers where the first pointer moves at twice the speed of the second pointer. If both pointers meet at some point, a cycle is found in the list.

Step-by-step approach:

1. First, we need to detect if a loop exists, if it does, we will use a helper function.
2. Inside the helper function, we will calculate the length of the loop, let's say the length of the loop = k.
3. Next, we need to find out the starting node of the loop. If we do that, then the node before the starting node must be set to NULL to break the loop.
4. Initialise 2 pointers — ptr1 & ptr2 to head.Move ptr2 k times ahead, while ptr1 is still at head.
5. Run a loop, so that if ptr1 & ptr2 meet, then that would be the starting node of the loop.
6. Finally, we find the previous node to the starting node of the loop and make the last node point to NULL.

Code:

Complexity Analysis:

Time Complexity: O(n).
n is the total number of nodes in the linked list.

Auxiliary Space: O(1).

If you liked this article, please click the “clap” button a few times.

Gives me enough motivation to put out more content like this. Please share it with a friend who you think this article might help.

Connect with me — Varsha Das | LinkedIn

Thanks for reading.

Happy coding😁