Solved

loop in link list

Posted on 2003-10-28
15
519 Views
Last Modified: 2010-04-15
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
Comment
Question by:Gaurav_Tayal
  • 4
  • 4
  • 2
  • +2
15 Comments
 
LVL 5

Expert Comment

by:snehanshu
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:


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
0
 

Author Comment

by:Gaurav_Tayal
ID: 9633360
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
 

0
 
LVL 45

Expert Comment

by:Kdo
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

by:snehanshu
ID: 9633638
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
0
 
LVL 5

Expert Comment

by:snehanshu
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

by:
migoEX earned 125 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
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 45

Expert Comment

by:Kdo
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

by:snehanshu
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 45

Expert Comment

by:Kdo
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

by:akshayxx
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

by:Gaurav_Tayal
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 45

Expert Comment

by:Kdo
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

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

759 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now