Gaurav_Tayal
asked on
loop in link list
Hi all
I have a link list containing a loop. Can anybody provide a method to detect it? I have read the solution from shajithchandran but I don't want to add another element.
Could somebody help me?
Gaurav
I have a link list containing a loop. Can anybody provide a method to detect it? I have read the solution from shajithchandran but I don't want to add another element.
Could somebody help me?
Gaurav
ASKER
Hi Snehanshu
Thanks for the help. But I haven't got exactly how this would solve the problem.
your second while loop says:-
while((isloop=0) && (myprev != mycur))
is the single equal in (isloop=0) accidental?
Just confirm this and then I will try to analyse the things further...
Gaurav
Thanks for the help. But I haven't got exactly how this would solve the problem.
your second while loop says:-
while((isloop=0) && (myprev != mycur))
is the single equal in (isloop=0) accidental?
Just confirm this and then I will try to analyse the things further...
Gaurav
Hi Gaurav_Tayal,
A simple program should do the trick. snehanshu is on the right track, though his algorithm looks like it will always return true (false positive).
Do you know how many items are on the list? Knowing the item count will allow you to write the test in such a way that you positively know how many iterations are required to find any loop.
MyNode *First, *Current, *Target;
int NodeCount;
int idx1, idx2;
Target = First;
for (idx1 = 0; idx1 < NodeCount; idx1++)
{
Current = Target;
for (idx2 = idx1+1; idx2 < Nodecount; idx2++)
{
if (Current == NULL)
fprintf ("Break found\n");
if (Current->Next == Target)
fprintf ("Loop Found\n");
Current = Current->Next;
}
Target = Target->Next;
}
Kent
Sorry Gaurav,
read
(isloop=0)
as
(isloop==0)
It may not be perfect: just typed it in the editor. But I guess the logic sould work :)
Let me know if there are any further problems/queries.
...Shu
read
(isloop=0)
as
(isloop==0)
It may not be perfect: just typed it in the editor. But I guess the logic sould work :)
Let me know if there are any further problems/queries.
...Shu
Kdo,
If the nodeCount is known then what's the problem?
You could just go to the last element and see whether its next is null or not!
A loop would mean that the last element does not point to null, but to a previous element.
...S
If the nodeCount is known then what's the problem?
You could just go to the last element and see whether its next is null or not!
A loop would mean that the last element does not point to null, but to a previous element.
...S
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Hi snehansu,
It's not reasonable to infer that the looping problem is because the next pointer in the last item in the list is non-null. While this might be the cause of the problem it certainly isn't the only possible cause.
Given a list of 100 items, if the integrity is broken because item 80 points to item 10, then two problems have resulted. From a data standpoint, the last 20 items are "lost" since no pointer from the root chain exists to link the remaining 20 items. From a process standpoint, examining 100 elements (NodeCount) will result in elements 10 - 29 being processed twice. This is what my code was intended to catch. (Ironically, the "lost" elements might be an intact chain while the "known" elements are guaranteed to have a problem!)
In reality, your program wouldn't process (NodeCount) items, it would process to end-of-list (next == NULL). But since there is no end-of-list marker, I was searching for another method of looking for duplicates.
Kent
Kbo,
There you go again! I resisted adding these lines in my previous post, but here goes:
If it is possible that the integrity of the list is broken, wouldn't it be equally possible that those same reasons that caused the break of integrity, caused nodecount to be 50 when actually there were 100 items? Why not search for a generalized solution when you can? Except for changing while to for, your concept isn't too different than mine.
migoEX's solution is something I would call a constructive/interesting/g ood alternate.
If possible, please don't confuse Gaurav further by continuing the argument.
...Snehanshu
There you go again! I resisted adding these lines in my previous post, but here goes:
If it is possible that the integrity of the list is broken, wouldn't it be equally possible that those same reasons that caused the break of integrity, caused nodecount to be 50 when actually there were 100 items? Why not search for a generalized solution when you can? Except for changing while to for, your concept isn't too different than mine.
migoEX's solution is something I would call a constructive/interesting/g
If possible, please don't confuse Gaurav further by continuing the argument.
...Snehanshu
Hi snehanshu,
EE works because those that participate often read the problem differently and come up with different solutions. Often, the problem as originally stated isn't the real problem, but a symptom. Having experts pose different solutions and different styles helps to isolate the problem. You posted a solution, so did I. MigoEX posted another solution that I find quite elegant.
There was nothing wrong with the logic in your original solution. If you'll go back and check you'll see that the FIRST line of my FIRST response was to credit you with a good approach and to point out that the code had a problem. It's pretty common around here for "off the top of one's head" code to have typos. Heaven knows that I'm susceptible to it. There was nothing negative meant and no matter how many times I re-read my post I can find nothing negative or accusatory in it anywhere.
The original post asked a question and I offered an alternate solution. YOU asked a question and I answered it.
I don't know what I've done to incur your wrath. Please fill me in. And please enlighten me as to what "There you go again!" means in your current context.
Kent
a bit late to join the party..
this is a well known interview problem with more than one solutions.. the most popular one (the one interviewers are eager to listen)...is the one migoEX suggested...
try writing C code for it, and get back to us if u get stuck.
this is a well known interview problem with more than one solutions.. the most popular one (the one interviewers are eager to listen)...is the one migoEX suggested...
try writing C code for it, and get back to us if u get stuck.
ASKER
Hi all
I have tried migoEX solution & it turns out to be:
struct node * t1, *t2;
int found = FALSE;
t1 = t2 = first;
while(t1 && t2->next)
{
if(t1->next == t2->next->next)
{
found = TRUE;
break;
}
else
{
t1 = t1->next;
t2 = t2->next->next;
}
}
I hope I have got the code right. Please check this and tell whether I am right or not.
Gaurav
I have tried migoEX solution & it turns out to be:
struct node * t1, *t2;
int found = FALSE;
t1 = t2 = first;
while(t1 && t2->next)
{
if(t1->next == t2->next->next)
{
found = TRUE;
break;
}
else
{
t1 = t1->next;
t2 = t2->next->next;
}
}
I hope I have got the code right. Please check this and tell whether I am right or not.
Gaurav
Close. Very close.
The only thing that I can see is that you never test (t2 == NULL). If the linked list is structurally sound, the program could wander off into space. Just change the while() statement to:
while(t1 && t2 && t2->next)
Congratulations!
Kent
Not sure what you mean by you don't want another element. If you are talking about no extra element in the list, then perhaps this would help:
For each item of the link, iterate from the first upto it to see if current item links to any of the previous ones. Break if it does.
Perhaps something like:
MyLink myfirst, *myprev, *mycur;
int isloop=0;
//code to initialize myfirst
//the check starts from the second member of the linked list
mycur = myfirst.next;
while(mycur !=null)
{
myprev = &myfirst;//get first
while((isloop=0) && (myprev != mycur))
{
if (myprev == mycur)
isloop = 1;
myprev = myprev->next;
};
if (isloop)
break;
mycur = mycur->next;
};
//isloop is 1 if there is a loop.
Hope this helps,
...Snehanshu