Detect and Remove Loop

Moderate

0/80

Average time to solve is 10m

Contributed by

210 upvotes

Asked in companies

Problem statement

Given a singly linked list, you have to detect the loop and remove the loop from the linked list, if present. You have to make changes in the given linked list itself and return the updated linked list.

Expected Complexity: Try doing it in O(n) time complexity and O(1) space complexity. Here, n is the number of nodes in the linked list.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains two values: the number of nodes in the linked list and the value of the kth node from which the last node connects to form the loop while the second line of input contains the given linked list.
The value of k should be greater than or equal to 0 and less than equal to n. For, k equal to 0, there is no loop present in the linked list and for k equal to n, the last node is connected to itself to form the cycle.

Output Format:

The only output line contains the linked list after removing the loop if present.

Constraints:

1 <= N <= 100000.
1 <= ‘VAL’ <= 1000 .  

Time limit: 1 sec

Sample Input:

6 2
1 2 3 4 5 6

Sample Output:

1 2 3 4 5 6

Explanation:

For the given input linked list, the last node is connected to the second node as:

Now, after detecting and removing this loop the linked list will be:

Hint 1

Hint 2

Hint 3

Think of checking each node as the starting point for the cycle.

Approaches (3)

Approach 1

Approach 2

Approach 3

Outer And Inner Loop

We are going to have two loops outer-loop and inner-loop

Maintain a count of the number of nodes visited in outer loop.
For every node of the outer-loop, start the inner loop from the head and maintain a prev node to store the previous node of the current outer loop node.
If the inner-loop visits the node next to the outer-loop node, then a cycle exist,we will simply set the prev node's next as NULL that will break the cycle and return the linked list else repeat the process for the next iteration of outer-loop.
If outer-loop reaches the end of list or null, then no cycle exist, return head.

Time Complexity

O(N*N), where N is the total number of nodes.

For every iteration of outer-loop we are iterating the linked-list again.

Space Complexity

O(1), As we are not using any memory to store anything.

(100% EXP penalty)

Detect and Remove Loop

Console