This trick is called Floyd’s tortoise🐢 and hare🐇, which is an algorithm to determine if a linked list is circular.

The algorithm requires two pointers called tortoise and hare. These two precede following the linked list, the tortoise goes to the next node while hare jumps to the second following node in each cycle.

If the linked list is circular, i.e., the last node of the linked list points the first node of the linked list, the tortoise and hare must meet at the first node.

Proof

Proof is quite easy. I’ll leave a hint.

• Hint
• Proof

Usage of Floyd’s tortoise🐢 and hare🐇

leetcode problem 287 (Find the Duplicate Number) can be solved applying the same approach.

Figure out linked list from function

The problem provides $f: [0, n] \rightarrow [1,n]$ discrete function with n+1 descrete elements in its domain. According to the pigeonhole principle, since the target set of the function is $[1,n]$, there will always be at least two elements in its domain which give the same output in the function. This is the duplicate mentioned in the problem.

Let’s think of linked list in which the next node is the output of the function.

Since we know that only one element(assured in problem) in the target set is pointed by multiple elements in the domain, we can surely say that there is a loop in our linked list.

Here is a diagram of the linked list drawn from the function.

How to solve