algorithmfloyd-cycle-finding

Floyd's cycle finding algorithm - Need for two pointers?

I was going through Floyd's cycle finding algorithm today and had a doubt. Why would he need two pointers and move them at different speeds?

He can instead create two pointers keep one static and compare the pointer of it with another pointer, which he increments? I mean even that will result in finding cycles right?

Solution

  • The reason they need to move is that the cycle doesn't necessarily have to loop the entire list of nodes.

    For example, let's say we have 4 nodes A->B->C->D->B

    If we kept one pointer pointed at A, we'd never detect the cycle.