Mark each element as you visit it; keep traversing; if you reach an already marked element, the list has
a cycle in it.
Second constraint:
The list is in read-only memory, and you cannot mark elements.
Usual second answer:
As you visit each element, store its address in an array; check each successive element to see if it is
already in the array. Sometimes poor candidates get hung up at this point on the details of hash tables
to optimize array lookup.
Third constraint:
Uh-oh! There is a limited amount of memory, and it is insufficient to hold an array of the necessary
size. However, you can assume that if there is a cycle, it is within the first N elements.
Usual third answer (if the candidate gets this far):
Keep a pointer at the beginning of the list. Check this pointer for a match against the next N - 1
elements in the list. Then move the pointer on one, and check against the next N - 2 elements. Keep
doing this until a match is found, or all N elements have been compared to each other.
Fourth constraint:
Oh no! The list is arbitrarily long, and the cycle might be anywhere in it. (Even good candidates can
get stuck at this point).
Final answer:
First, eliminate the pathological case of a 3-element list with a cycle from element 2 to 1. Keep two
pointers. One at element 1 and the next at element 3. See if they are equal; if not, move P1 by one and
P2 by two. Check and continue. If P1 or P2 is null, there is no loop. If there is one, it will definitely be
detected. One pointer will eventually catch up with the other (i.e., have the same value), though it
might take several traversals of the cycle to do it.
There are other solutions, but the ones above are the most common.
Programming Challenge
Knocked for a Loop