How to check if a singly linked list is looped?

Question

Java

Good day to all.
They asked me recently one problem, over which I have been toiling for several days. There is a singly linked list that is used in a multithreaded system and is modified by multiple threads. We need to determine if the list is looped (the last element points to the first one).
The option of equating referrals by two markers ala for each turn of the outer cycle that takes the i-th element, all subsequent referrals are selected and compared by the inner cycle, did not fit. I have already thought about the "local interpretation" of this method, where, when selecting each subsequent element from the list, a comparison is made with subsequent referrals, but there are doubts about the correctness of the approach.
I would be grateful for any suggestions regarding the solution of this problem.

Answer 1

The algorithm is as follows:
1) Each element of the list is placed in our wrapper, one of the fields of which will be a ThreadLocal variable - a flag. Initially, the flag is disabled.
2) When we visit an element, raise the flag.
3) If a raised flag is found, the list is looped. If you hit next==null - no.
If such an action on the list needs to be performed more than once, then the raised flag should have 2 values, which we alternate at each start.

Answer 2

You can't test for looping multithreaded, since it's not an atomic operation anyway.
You will have to make access to the method synchronized. And then you can:
1. Make a dummy flag for each node that we have already been here
2. Start up two iterators. The first according to the rule i=i+1, the second according to the rule i=i+2. And if the second catches up with the first, then you have a cycle.
3. Option to remove links to next.

Answer 3

If you knew the number of elements in the chain, then passing through it and counting the steps could already be understood.