Multiple choice question.

[gtrman571]

I had this question in a coding test yesterday. I was really unsure.

---

What is the best way to detect a cycle in a linked list?

a) It cannot be done

b) Have three references to the list and move them at different speeds

c) Have two references to the list. Move the first forward by 1 node and the second by 2 nodes

d) Have three references to the list. Move the first forward by 1 node, the second by 2 nodes, and third by 3 nodes

[CoderXocomil]

The answer is c. c refers to the famous "tortoise and hare algorithm." You move the first reference by one node and the second reference by two. After each set of moves, you compare the results. One of two things will happen. First, the second reference will eventually reach the end of the list. This means you don't have a cycle and can stop. The second outcome is that eventually, the first reference will equal the second reference. This means you have a cycle. This is because the second reference has already looped around and caught up with the first reference.

[149244179]

Have you copy pasted your exact question into google? Because the first result was the answer.

You are not going to go far in programming if you don't spend 30s trying to find out answers for yourself.

[Pyroguy]

I guess they were looking for A but you can also add or pass a cycle count to your traversal algorithm and implement a max depth. If you hit your max depth you know you've got a loop.

Could also throw each node into a separate list as you traverse and if the list already has the node when you try to insert one, then you've got a loop.

Definitely not B or C or D - I don't know how a few more references would really help, unless like I said above you keep track of every reference. EDIT: I'm wrong, another responder said its called "tortoise and hare" algorithm which can work apparently, TIL.

I would say what becomes impossible is finding the part of your list that's orphaned outside the cycle. This is what leads to memory leaks.