i need write a program to check if a list is acyclic, which means that a travel from any node in the list must not come back to the node itself.
a node is a struct type defined like that
but i am not allowed to allocate memory proportional to the list size and i even don't know the list size.
i now have no idea to do it, can anything give me a hand, please?
Here's a very simple one. http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm
Understand the whole thing where the first pointer will 'catch-up' to the second deal.
but i am not allow to allocate memory proportional to the list size, so i may not use that algorithm.
There is no memory allocation involved in that (O1 storage). If you have a hard time conceptualizing the text, make sure to read 'visualizing the algorithm'
Thank you for your advise and i have make it. the assignment need me to do this task by two different methods, are there any other method you can suggest?
Does it also have to be O(1) storage? Does it have to be completely different from that other technique?
I don't think so, i am only not allowed to allocate memory proportional to the list size and i even don't know the list size, and i can't modify the list , that is all