Cycle detection

I was wondering if anyone knew any good cycle detection algorithims for an array of linked lists. If anyone knows any good links or code (even pseudocode) it would help me out tons! I need an algorithim that will detect a cycle not just in a element of the array (its not possible in my situation) but the array as a whole.

for something like this...
ListType *Wait_For;
ÏWait_For= new ListType[Max];

Hmm...not something I've particularly looked at but my thoughts would be to do it as follows.

Start at the first element of the array and mark the first element of the list. Follow its next pointer and mark that and so on. When you reach the end of a linked list go to the next element in the array and continue marking.

If you reach the last element of the array and the last element of the linked list then there are no cycles. If you encounter a marked node before that then there is a cycle.

No idea if this works or how well since its early but it should give you a good starting point if nothing else,

-KM-

A simple technique for detecting infinite loops inside lists, symlinks, state machines, etc. For example, to detect a loop inside a linked list:

• make a pointer to the start of the list and call it the hare
• make a pointer to the start of the list and call it the tortoise
• advance the hare by two and the tortoise by one for every iteration
• there's a loop if the tortoise and the hare meet
• there's no loop if the hare reaches the end

This algorithm is particularly interesting because it is O(n) time and O(1) space, which appears to be optimal; more obvious algorithms are O(n) space. This problem is called Tortoise and Hare problem and this link will be quite useful for you. http://c2.com/cgi/wiki?TortoiseAndHare

can u please the hare and tortoise solution more clear with an example