actually my question is this :suppose u have a linked list like this :1---2345---6---7--8 ^ |
| | | v 10 --- 9 then how can u find the cycle here ..
On 5/14/06, deepblue [EMAIL PROTECTED] wrote:
Hi Arulanandan P,I feel the best possible answer to this
But how do you detect where the cycle starts (or ends) ?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from
Could you please pass on the link?On 5/15/06, pramod [EMAIL PROTECTED] wrote:
OK. I got this on the net. Too good. Time complexity is also O(n).findloophead(x, y) {a = xb = ywhile (next(a) != b) {/* while b is not loop head */t = midpoint(a, b)if (find(next(y), t, b)) {/* if t is in the loop */
b
Its a slow algo for finding cycles in a linked list, the previous one is faster.On 5/15/06, Kapil [EMAIL PROTECTED]
wrote:try Breadth First Search, and if in between u find that some node you
have traversed then yes there is a cycle.
--~--~-~--~~~---~--~~
You
@Kapil
How do you intend to do a BFS in a linked list (its not a Bin Tree i
suppose or a graph)
@Pramod
Can you please detail as to what does your program do?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Arulanandan P wrote:
Hi ,
what is the best way to find out if there are any cycles in a linked list?
regards
arulanandan
Your question doesn't have any meaning because a list has no cycles.
But if you mean how to determine if a _graph_ has no cycles, then the
usual method is to use a
Hi Arulanandan P,
I feel the best possible answer to this is:
Take 2 pointers and increment the first with 1 node and increment the
second with 2 nodes. Then after every increment check if the values of
the pointers are equal. And if they are equal then you can say that the
linked list has an