CIRCULAR LINKED LIST - Doubt in implementation

#1

What is the problem with the code?https://ide.codingblocks.com/s/98274

Also do we have to build a cycle on our own by taking the inputs and then detect it using the algo?

#2

This is how I have done the program. However the code is not working. The functions which I have used to code for the question are in main(). buildlist(), buildcycle() are probably working fine. Please have a look at the code. https://ide.codingblocks.com/s/98277

#3

First answering to your doubt on inputs- just scan the input so that any input can be used.
Secondly in your code- can you please remove or comment out all the unnecessary functions, it’s confusing to find out the needed functions. Anyways, what I can tell you is simply check if slow->next and fast->next->next ever become equal. If they do, it means a loop is present. So pass slow as a parameter in a separate loop.
In that particular loop, take pointer1= head, pointer2= slow. Start iterating pointer2->next until it becomes equal to pointer2(means reaches itself back in the circular loop) if it reaches itself back, and pointer2->next is still not equal to pointer1 this means that you still haven’t found the loop start. Now do pointer1->next, that is, you have moved on next position of head. Again iterate pointer2. If pointer2->next becomes equal to pointer1, it means you have found the loop start at pointer1 and loop end at pointer2->next. Thus make pointer2->next equal to NULL.

I have given you almost complete info about this question, now try implementing it or correcting your code. If you’re not able to solve, ask me to dry run it for you.

#4

This is the code with only the required functions. https://ide.codingblocks.com/s/98731.
Using buildlist(), I have taken 1 linked list as input, which creates 1->2->3->4->5->2->1.

Now I identify the first duplicate present in the linked list, as it helps us identify the point from where the cycle originates. The first duplicate identified is 2. Now, I connect the node before 2, i.e, 5 to 2, creating a cycle. This is done using build_cycle() function.

Now I trace the the cycle using Floyd Cycle Detection Aglo. The function used is detect_cycle(). I can’t seem to figure out the problem with code. Please check.

#6

OK, did you even look at this book that I wrote above?
Anyways, first of all in detect_cycle() function, do you realize that there can be multiple same data, so your condition won’t work in many conditions, you need to put the condition that
while(slow!=null && fast!=NULL && fast->next!=NULL )
{
slow=slow->next;
fast=fast->next->next;

if(slow==fast)
// Means you have detected a loop.

//Now start acting on the loop, as I have explained above.
}
Correct it, if it doesn’t work, ask again on chat.

#7

Thanks for your effort… But the entire time I kept asking about the Floyd Cycle Detection algo… And u suggested me to use a method which had higher time complexity… Finally today I identified the error in my code. However I would still thank u.

#8

Hi
What doubt you have?As per your above comments, you seem to have figured it out already