If the loop does not exist then I understand but if there is any loop then I think it would not be N. Say if you have 100 elements and the loop exists between 100 is pointing to 1. Then I believe it would jump many times!! so the worst case complexity would be much more. Any thoughts
Hi @Rajesh_Goel,
This is Fatimah Abdullah from Educative. Thank you for reaching out to us!
In response to your feedback, let’s consider that the list has n nodes, and the loop is of m length. Then, we can be sure that m is less than or equal to n as well.
Each step the pointers take, the distance between the fast and the slow pointers will increase by 1. When the distance is divisible by m , then the fast and slow pointers will be on the same node and the algorithm terminates. The distance will reach a number divisible by m in <= m steps. And, that is in O(n)
I hope that clears it up for you. If you have any further queries, please let us know.
Best Regards,
Fatimah Abdullah | Developer Advocate
Educative