How to determine a linked list has a cycle without marking any nodes? This is a classical interview question and one of my friend brought it to me.

When I came across the question, I thought that we might count the nodes. If the our counter goes behind the linked list’s size, we could say that a cycle exists somewhere in the list. But, we have to know the size of the list at the first place, so it turns out to be a improper solution since the only thing provided in this problem, typically, is the head of the list.

We searched through the web and eventually found an amazingly simple algorithm to solve the problem from DaniWeb. I’m going to repeat it here.

To solve the problem, we need two iterators to go through the linked list. One iterator acts normally, we call it single-stepping iterator: it’s going to run from one node to the next; the second iterator, we call it double-stepping iterator: it will skip one node and goes to the second next node at each step. Then, if this two iterators meet before the end of the list (there is no end if it is circular), there is a cycle.

That’s it, and it works!