Simple huh...
Cycle in Linked List
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
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 :-)
How is that useful Kyle? Just to see if a linked list is a circular linked list? If you wrote the linked list, couldn't you assume it is circular or not? It is a cool algorithm though.
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..
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.
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.
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 cLike I say, I've seen this algo before, so what am I doing wrong here?
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
