Link Detection Algorithm

Question

I read a question from an online interview about how you would find if there is a loop in the linked list, and the solution (the Floyd loop search algorithm) consists of two pointers, one is 2 times faster than the other, and check to meet again.

My question is: why can't I just keep one pointer fixed, just move the other pointer forward 1 step each time?

Answer 1

Because the first (non-moving) pointer may not be inside the loop, so the pointers never met. (Remember that a loop can only consist of part of a list.)

Answer 2

Because maybe not a full linkList is inside the loop.

For a linked list of lasso detection algorithm, you will need two pointers:

While the first pointer is where the cowboy is, no loop is detected. But if you move it a step forward, it will eventually enter the cycle.

---

BTW, lasso is a termicus technicus from graph theory, a cowboy is not.

Answer 3

Because the loop may not contain the element that the first pointer points to.

For example, if the first pointer points to element 1, and the linked list has a loop later (1-> 2-> 3-> 4-> 2), your algorithm will not detect it.