Archived

This topic is now archived and is closed to further replies.

Guest Anonymous Poster

Cycle in Linked List

This topic is 6573 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

When you start the traversal, store a pointer to the first node (call it head or whatever), then test for it at each node you visit. If you find a match, you have a cycle, otherwise, you don't

Simple huh...

Share this post


Link to post
Share on other sites
That method will not work in the general case. For example, say you have 2 items in your list a and b. a points to b and then b points to itself. As you can see, you'll never get to a and you will in an infinite loop.

The best way to solve this is have 2 points traverse the list. One of them is incremented by 1 and the other is incremented by 2. Traverse the list until they pointers point at the same item or one of them reaches the end of the list. Proof of this is left as an exercise to the reader :-)

Share this post


Link to post
Share on other sites
Kyle, you found the error in my code...and i've found the error in yours. lol

I incorectly assumed he was looking for the WHOLE list accidentally circling back...i see that was way to simple. But you are assuming that a cycle will always be directly onto itself. What about a->b b->c c->a, etc. So REALLY ... to detect the GENERAL case where ANY form of cycling occurs, the only possible algorithm is to do the equivelent of marking each node you visit as VISITED...either by setting some value of it, or storing a pointer to it in another list. This is a VERY inefficient thing to do (grows in size by n, and in speed by n^2), but it is the ONLY general case algorthim. Oh well..

Share this post


Link to post
Share on other sites
I think you misunderstood the algorithm I mentioned. In your example (using the algorithm I stated):

Counter ptr1 ptr2
0 a a
1 b c
2 c b
3 a a

So after a few iterations we find that there is a cycle in the list. I've proven this myself rigorously and it works in the general case.

If you want to find _where_ the cycle occurs (which might have been what the original poster wanted...), then you'll have to use a method similar to Xia's.

Share this post


Link to post
Share on other sites
You are basically applying a graph traversal algorithm to a linked list. Funny a linked list is a graph with no weights and more restrictions on how to place edges between vertices. The visited rule works well here but as Xai said it increases processing considerably. Use bit operations to set the visited bit for a small amount of performance increase.

Using the increment pointer twice method works as described but I caution you to be sure to check the validity of the pointer beyond the current node before you dereference it. I always found that dereferencing ptr->next->next was dangerous because you don't know if ptr->next is null unless you test it. If your on node ptr then you know that by its constructor ptr->next is valid though you can't assume ptr->next->next is the same.

Kressilac.

Share this post


Link to post
Share on other sites
What am I missing here? I've seen that alogrithm before, but heres where I have a problem:

a->b
b->c
c->b

now when you try the one-two pointers.


Counter ptr1 ptr2
0 a a
1 b c
2 c b
3 b c
4 c b
5 b c

Like I say, I've seen this algo before, so what am I doing wrong here?

Share this post


Link to post
Share on other sites
b->c and c->b, therefore pointer 2 which makes 2 jumps should be going from a to c (a->b b->c) then to c again (c->b b->c) so it keeps going to c ad infinitum... well, until the first pointer gets to c, where you pick up the cycle and deal with it!

Regards

Starfall

Share this post


Link to post
Share on other sites