1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.