According to some online sources I referred the runtime complexity of Floyd's cycle detection algo is O(n). Say,
p = slow pointer
q = fast pointer
m = the distance from start of linked list to first loop node
k = the distance of the meeting point of fast and slow nodes from the first loop node
l = length of loop
rp = number of loop rotations by p before meeting q.
rq = number of loop rotations by q before meeting p.
Run time complexity should be = m+rp*l+k How does this value be O(n)?
If the list has N nodes, then in <= N steps, either the fast pointer will find the end of the list, or there is a loop and the slow pointer will be in the loop.
Lets say the loop is of length M <= N: Once the slow pointer is in the loop, both the fast and slow pointers will be stuck in the loop forever. Each step, 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.
So, getting the slow pointer to the loop, and then getting the fast and slow pointers to meet takes <= N + M <= 2N steps, and that is in O(N)
In fact, you can get a tighter bound on the step count if you note that when there's a loop, the slow pointer will get to it in N - M steps, so the total step count is <= N.