In the best method to detect a cycle in a linked list, we do the following:
I'd like to know why this works. Some theoretical logic behind this?
Floyd method helps you detect that there's a cycle, but because there may exist some nodes before start of cycle, it can not directly give you the length of cycle. So you should calculate the length in the next step.
Now we want to spot start point of cycle. Consider, length of cycle is K
and number of nodes from head node to start of cycle is L
, now if you move both pointers forward, they meet at the start of cycle, because, the head pointer has to go forward L
nodes and the pointer which K
steps ahead has two possibilities. It sure will be on start of cycle after L
node because: Choice 1: if it is in cycle, it's on the node K-L
of cycle and K-(K-L) = L
. Choice 2: if it is out of cycle, L-K
nodes is remaining to the start and L-K + K = L
.