Measuring the length of a "loop" in a linked list in $O(n)$ Time? I have been given a linked list in Python. At some point, one of the nodes is linked to a previous node creating a &quot;tail&quot; and a &quot;loop&quot;:
Node1 -&gt; Node2 -&gt; Node3 -&gt; Node4 -&gt; Node5 -&gt; Node6 -&gt; Node3
Node1 and Node2 are considered elements of the &quot;tail&quot;, while Node3, 4, 5 and 6 are considered elements of the &quot;loop&quot;.
My task is to measure the length/number of elements in the &quot;loop&quot;.
My approach was to go through the linked list and catch, when a node points towards a node, I have already passed.
However, to check if a node has been already passed, I have chosen to store all passed nodes into a list/array.
Whenever I approach the next node, I check, whether the next node is already stored in the list/array.
This approach does work, however I was hinted, that there is a way to solve this in linear complexity.
If the linked list consists of n nodes
I am adding 1 element to a list with each node
and I am also checking every element in this list with each node
I assume the complexity is something like : $\frac{n^2 + n}{2}$ which is clearly not ideal.
However I struggle to find a way to check whether I have already passed a node, without checking all previous nodes with every step. Which again would make it necessary to

Keep a list of all previous nodes and
Loop over this list in each step

which then again would increase the complexity.
Is there a way to check, whether I have already passed a node, without checking on all previous nodes?
There is a surprisingly simpler solution! Are you familiar with the tortoise and hare algorithm?
Start thinking from there: Understand this algorithm and why it works, and then you might get an idea or two for the problem