Linked list loop detection algorithm

问题:

I read some interview question online about how would you find if there's a loop in a linked list, and solution (Floyd's cycle-finding algorithm) is to have two pointers, one is 2x faster than the other, and check if they meet again.

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

回答1:

Because the first (non-moving) pointer might not lie within the loop, so the pointers would never meet. (Remember that a loop may consist of only part of the list.)

回答2:

Because maybe not the complete linkedList is within the loop.

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

As long as the first pointer is where the cowboy is, no loop is detected. But if you move it stepwise forward, it will eventually enter the loop.

---

BTW, lasso is the terminus technicus from graph theory, cowboy isn't.

回答3:

Because the loop may not contain the element pointed to by the first pointer.

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