Cycle Detection and Removal in Linked List

#1

Given the head pointer to a linked list , complete the function to check whether there is a cycle present in the linked list. If so , modify the linked list to remove the cycle.

Note : You are only supposed to update the designated function. Do not change/alter the remaining code or your program may not work.

Input Format
Your function accepts one single argument that is the head pointer to the linked list.

Constraints
Your function should run in O(n) time.

Output Format
Your function should return a boolean value - True/False , indicating the presence of the cycle.
True if cycle is present, False otherwise.
If true , remove the cycle as well.

Sample Input
Consider a linked list like
1 -> 2 -> 3
^ |
| v
5<- 4
Sample Output
Your function should return True for the above linked list and remove the cycle as well.

The new linked list should look like - 1->2->3->4->5-> NULL
Explanation
Clearly there is a cycle present. We return true to indicate it and remove it.

link- https://online.codingblocks.com/app/player/74030/content/128054/8696/code-challenge

code- https://ide.codingblocks.com/s/347929

#2

hello @anubhavb0011

image

in while loop it should be && in place of ||.

ur logic for removing cycle is not correct.pls check

#3

why removal logic is wrong it will simpily point the last node to NULL

#4

yeah this is correct, but the thing is u need to find the last node first (imagine a list something of p shape in that case u need to first detect the ending of the list).

#5

i have corrected the code but most of Test case giving wrong answer
code-https://ide.codingblocks.com/s/347951

#6

image

this loop wil run infinetely because slow and fast in the if (line 17) are always equal.

the idea is inside if.
initilise ur slow with head. and
while(slow->next!=fast->next){
slow=slow->next;
fast=fast->next;
}
and then simply do fast->next=NULL (to break the loop)

1 Like
#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.