Is there a loop in the chain?

Question

A sequence of boxes is linked: each box contains a pointer to a "next" box. Starting from the first box and following pointers, you either reach a box marked "end" or you go round forever, because some box points back to an earlier one.

You cannot mark boxes or remember which ones you have visited, and there may be millions of them. You may keep only a fixed small number of pointers into the chain.

How do you decide, in a bounded amount of time, whether the chain contains a loop? As a follow-up, how would you find where the loop begins?

Accepted Answer

Use two pointers: a "tortoise" that advances one box per step and a "hare" that advances two. If the hare reaches the end, there is no loop. If there is a loop, the hare enters it first, the tortoise follows, and the hare then gains one box per step on the tortoise around the loop, so they meet within one lap. Why they must meet. Once both pointers are inside the loop, the gap between them (measured around the loop) changes by exactly one each step, because the hare moves two and the tortoise one. A gap that shrinks by one each step reaches zero within at most the loop's length in steps. So t…

Is there a loop in the chain?

Your answer

Discussion

Learn the concepts

Related questions