Programming MODBasic Intermediate

Problem - 4785

Given a pointer pointing to the header of a linked list, how to detect whether the linked list has a loop?

An additional question: how can math knowledge help here?


One obvious solution is to let the pointer continuously move forward and, at the same time, save all the nodes it has visited. If the pointer reaches the end of the linked list, we know there is no loop. Otherwise, if the pointer visits a saved node again, a loop is detected.

This solution works, but both memory inefficient (need to save all the visited nodes) and time inefficient (needs to compare with all the saved nodes when the pointer moves to the next node).

A better solution is to introduce a new pointer, initially also point to the header of the list. Then we can have the two pointers move at different speed. For example, the 'faster' pointer moves two steps every time and the 'slower' pointer moves one step each time. If the faster pointer reaches the the end of the linked list, we know there is no loop. Otherwise, if the two pointers point to the same node at any time, a loop is dected.

Now we show that if there is a loop, the two pointers will eventually meet. Without loss of generality, let's assume there exists a loop containing $N$ nodes. In this case, eventually the two pointers will both enter the loop and remaining in it.

Let's mark the first node in the loop as $1$. When the slower first enters the loop, its location is $1$. Let assume the location of the faster pointer as $k$ at this moment. Because it is a loop, therefore after $x$ step, the location of the slower pointer will be $(x\mod{N})$ and the faster pointer will be at $(2x\mod{N})$. Then whether the the two pointers will meet is equivalent to whether the following equation always has a solution: $$x\equiv 2x\mod{N}$$

Of course the above equation is always solvable. Therefore, as long as there is a loop, the two pointers will eventually meet.

report an error