Hi,
I wanted to know why in the algorithm(Floyd’s cycle finding) to find the loop in the linked list we use 2 pointers? and why we have to move the fast pointer by two? 
Can anyone help me? please.
If you only used one pointer, you would have no way of knowing the difference between traversing a REEEEAAAAALLLLYYY long list or being stuck in a loop.
With two pointers, you can tell the difference between the two cases. The first one plods along one link at a time. The second zooms ahead two at a time. That second pointer will either smash into the null at the end of the list (and throw a null pointer exception) if there is no loop or it will get stuck infinitely circling around a loop.
Depending on where that loop is located in the chain (either a full circle where the last link points back around to the first link or any link in between) the slow pointer may not have reached it yet. That is OK because the fast pointer is still zooming around the loop. Eventually, the slow pointer will enter the loop too. Because the slow pointer is moving one link at a time and the fast pointer is moving two at a time, you can be assured that both pointers will eventually point to the same node and trigger the exit from the method. Even if the first pointer jumps over the slow one in it’s first pass, they will eventually be coincident.
It can be helpful to draw out a few different scenarios on paper to help you visualize it. Draw rectangles to represent the links of the list. Make a few different scenarios - one with no loop (like a standard linked list would be), one that is circular, and one with an arbitrary loop somewhere in the middle. Next use a penny and a dime (or your favorite Monopoly pieces) and simulate the two pointers traversing the list.
1 Like