In an interview I was asked to detect the loop node in the linked list and count the number of nodes in the loop. As i was unaware of the flyod algorithm, I tried to figure out my own approach.
The idea is in this scenario, the address of two nodes will be pointing to the same node(loop node).
Eg.
1-->2-->4-->5-->7-->3-->4
Here 2->next and 3->next is same, which is the address of 4. Which means there is a loop in the linked list and 4 is the loop node. And traversing from 4 to 4 will give the number of nodes in loop.
Is there a way we can go ahead with this approach ????
Of course you can trivially find a cycle by maintaining a set of addresses already visited. Since you are interested in loop size, you can make this a map instead: address->count. The count is how many nodes have been visited upon visiting the one at the corresponding address. When you discover a node already in the table, you can get the loop size by subtracting the count in the table from the current one. Of course you can get the same effect by maintaining a "visited" bit and count in the nodes themselves. Then no separate map is needed.