Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

Posted on 2003-10-28
Medium Priority
574 Views
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
0
Question by:Gaurav_Tayal
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 4
• 4
• 2
• +2

LVL 5

Expert Comment

ID: 9633162
Gaurav,

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:

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
0

Author Comment

ID: 9633360
Hi Snehanshu

Thanks for the help. But I haven't got exactly how this would solve the problem.
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

0

LVL 46

Expert Comment

ID: 9633393

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
0

LVL 5

Expert Comment

ID: 9633638
Sorry Gaurav,
(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
0

LVL 5

Expert Comment

ID: 9633692
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
0

LVL 5

Accepted Solution

migoEX earned 500 total points
ID: 9633875
I cas suggest following algorithm:

1) define 2 pointers to list elements, and init them to point to the first element
2) advance first pointer by 1 element each step, and the second - by 2 elements
3) if the second (the faster) pointer will reach end of list - no loop
if there's a loop - the pointers will meet on one of the elements.

regards
0

LVL 46

Expert Comment

ID: 9633986

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
0

LVL 5

Expert Comment

ID: 9634157
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/good alternate.
If possible, please don't confuse Gaurav further by continuing the argument.
...Snehanshu

0

LVL 46

Expert Comment

ID: 9634378

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

0

LVL 8

Expert Comment

ID: 9635370
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.
0

Author Comment

ID: 9647845
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

0

LVL 46

Expert Comment

ID: 9650255

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
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: Iâ€™ve never triâ€¦
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and infâ€¦
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
###### Suggested Courses
Course of the Month8 days, 14 hours left to enroll