The Tale of the Teleporting Turtle.

The obvious solution is to run down the list and mark each node as you find it. If you find a node with a mark, you have found a cycle. If you reach the end of the list, there is no cycle.

The problem is that you have to mark the nodes. Perhaps you're not allowed to do that. OK, then make a note of each node you visit, and every time you step to another node, check to see if it's on your list.

The problem now is that you don't know how long your list will become. More, checking your list gets more and more onerous. In fact the number of checks grows quadratically with the length of your list. Not efficient, certainly not practical.

But in the late 1960s Robert W. Floyd came up with an algorithm that required no more storage than two pointers to the list, and which worked in time O(n), guaranteed no longer than a constant times the length of the list. Nicknamed "The Tortoise and the Hare," this clever algorithm is used in many applications, from testing the cycle length of a pseudorandom number generator to factoring numbers, from analysing group structures to determining whether the phase space of an orbital system is periodic.

Briefly, Floyd's algorithm starts with two pointers - the eponymous tortoise and hare - both pointing to the start of the list. For each tick of the clock the tortoise takes one step and the hare takes two. If the hare ever reaches the end of the list then clearly it can have no loop. But if there is a loop, eventually the hare will catch up with the tortoise. Thus if the tortoise and hare are ever pointing at the same node, there is a loop.

    tortoise = head
    hare = head
    Forever:
        if end==hare : return 'No loop' : else : hare = hare.next
        if end==hare : return 'No loop' : else : hare = hare.next
        tortoise = tortoise.next
        if hare==tortoise: return 'Loop found'

Being O(1) in space and O(n) seems optimal - the question is now whether we can make it run faster. The answer is yes - we use a teleporting tortoise.

Well, obviously tortoises can't teleport, so we use a turtle instead, and since we use a turtle instead of a tortoise, we'll use a rabbit instead of a hare. (Work with me here ...)

So how does a teleporting turtle help us?

We start with the turtle and rabbit pointing to the head, and then on each clock tick we advance the rabbit by one step. After a while, assuming we've neither found the end of the list nor caught the turtle, we teleport the turtle to the rabbit's position, double the length of time we're willing to wait, then go again.

Here's the algorithm in pseudo-code:

    turtle, rabbit = head, head
    steps_taken, step_limit = 0,2
    rabbit = head
    Forever:
        if end==rabbit : return 'No loop' : else : rabbit = rabbit.next
        steps_taken += 1
        if rabbit==turtle : return 'Loop found'
        if steps_taken==step_limit:
            steps_taken = 0
            step_limit *= 2
            turtle = rabbit

In a sense, this is taking the naive idea and making it work.

The naive way to perform loop detection is to run around for what you hope is long enough, and if you don't succeed in either finding the end or finding a loop, you give up. The teleporting turtle idea is nearly the same, it's just that now instead of giving up you just double the time you're willing to spend, and try again.

The space complexity is still constant, although we do need two extra variables to keep the steps taken and the step limit. The time complexity is still O(n), although now on every clock tick we only take one step, not three.

Although following a link isn't much work when you're running around a linked list, the cycle-detection algorithm is also used in the Pollard rho and elliptic curve methods of factoring, in which the numbers are huge and the "list" is implicit. In these cases it's a huge saving to perform 1/3 of the steps (although in practice the saving isn't as much as 1/3).

So the teleporting turtle wins the day, and anyone who tells you that the tortoise and the hare method of finding loops in linked lists is the best you can do, hasn't done all their homework.

For more information than you could possibly want, wikipedia is your friend:

• Wikipedia on Cycle Detection

• The Teleporting Turtle