Detect and Remove Loop

Difficulty: MEDIUM
Avg. time to solve
10 min
Success Rate

Problem Statement
Suggest Edit

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.

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.

Input format:

The first line of input contains the linked list while the second line of input contains the value of the kth node from which the last node connects to form the loop. 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.

Sample Input:

1 2 3 4 5 6 -1

Sample Output:

1 2 3 4 5 6
For the given input linked list, the last node is connected to the second node as:

Alt Text

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

Alt Text

Reset Code
Full screen