Measuring the length of a "loop" in a linked list in $O(n)$ Time?

Question

I have been given a linked list in Python. At some point, one of the nodes is linked to a previous node creating a "tail" and a "loop":

Node1 -> Node2 -> Node3 -> Node4 -> Node5 -> Node6 -> Node3

Node1 and Node2 are considered elements of the "tail", while Node3, 4, 5 and 6 are considered elements of the "loop". My task is to measure the length/number of elements in the "loop".

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

1. Keep a list of all previous nodes and
2. 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?

Answer 1

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