• C

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?

Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.


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)
  mycur = mycur->next;

//isloop is 1 if there is a loop.

Hope this helps,
Gaurav_TayalAuthor Commented:
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...


Kent OlsenDBACommented:

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;

Determine the Perfect Price for Your IT Services

Do you wonder if your IT business is truly profitable or if you should raise your prices? Learn how to calculate your overhead burden with our free interactive tool and use it to determine the right price for your IT services. Download your free eBook now!

Sorry Gaurav,
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.
  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.
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.


Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Kent OlsenDBACommented:

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.

  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.
Kent OlsenDBACommented:

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.


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.
Gaurav_TayalAuthor Commented:
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;
      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.

Kent OlsenDBACommented:

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)

It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.