New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Detect and Remove Loop

Contributed by

srejanbera

Medium

0/80

10 mins

90 %

140 upvotes

+29 more

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:

Autocomplete

Console