CODEWITHSUNDEEP
algorithmdata-structureslinked-list
FallAndLearn
FallAndLearn

Reputation: 4135

Find loop in a linked list containing millions of nodes

This was asked to me during an interview. I know several approaches to solve this question. But the emphasis was that it is containing millions of nodes.

I know we can solve this using two pointers approach. Also we can solve this using HashMap. He wanted to know the optimized solution as the list is having millions of nodes.

After that, I also suggested dividing the list into multiple chunks and then apply multithreading to fasten the process. But he was not full satisfied. Is there any other way which I am not focussing on. Using mulitthreading we also have to maintain a visited set of next nodes as when dividing the list into chunks, it is possible that the loop is divided into two parts.

I am not asking for any implementation. Just provide me with some direction so I can ponder more on it.

Upvotes: 2

Views: 184

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59358

If you started off with Floyd's algorithm (the two-pointer thing), and the interviewer then wanted you to suggest something faster, then you went in the wrong direction. Maintenance of a HashMap would take way longer. Multithreading is also not useful, because it's a linked list and you have to walk it to divide up the work.

I would have started with Brent's algorithm, which follows fewer pointers than Floyd's algorithm, and is often faster because it's cache-friendly. Wikipedia has a good description of Brent's algorithm here: https://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm

It's also possible to speed up Brent's algorithm in various ways. Brent's algorithm ensures that you will visit no more than twice as many nodes as you really need to to find the cycle. By storing more than 1 previous node in a simple 1-way associative hash (no collision avoidance), for example, you can reduce this factor until it's arbitrarily close to 1.

Upvotes: 2

Related Questions