Detecting cycle in a singly linked list

Question

Detecting cycles in a single linked list is a well known problem. I know that this question has been asked a zillion times all over the internet. The reason why I am asking it again is I thought of a solution which I did not encounter at other places. (I admit I haven't searched that deeply either).

My solution is:

Given a linked list and pointer to some node, break the link between node and node->next(); Then start at node->next() and traverse till either you hit an end (which means there was no loop) or till you reach at node which means there was a loop.

Is there anything wrong/good about above solution ?

Note: Do join the link back once you are done.

• Eastern Monk: Most of the solutions suggest that the two "runners" with different speeds as the best solution. Happens to be O(n), Isnt my solution O(n) too ?
• Kendall Frey: I don't see any reason for breaking the link, just treat node as a sentinel. A problem: if node is a, then your algorithm will not work on a->b->c->d->e->c. Your algorithm will only detect loops where the last node points to the first node.
• Has QUIT--Anony-Mousse: This does not work, if the loop isn't global. Example: a -> b -> c -> b -> c -> b -> c -> b -> ... never returns to a.

Answer 1

That will work to detect complete cycles (i.e., cycles with a period of the whole list), e.g.:

A -> B -> C -> D -> A

But what if we have a cycle somewhere else in the list?

e.g.,

A -> B -> C -> D -> E -> C

I can't see that your algorithm will detect the cycle in this case.

Keep in mind that to detect the first case, we need not even break the link. We could just traverse the list and keep comparing the next link for each node with the head element to see if we'd started back at the start yet (or hit the end).

Answer 2

I guess the most trivial approach (not necessarily the best, but one that everybody should know how to implement in Java in a few lines of code) is to build a Hash Set of the nodes, start adding them until you find one that you already saw before. Takes extra memory though.

If you can mark nodes, start marking them until you find one you marked before (the hash map is essentially an external marker).

And check the usual graph theory books...

Answer 3

You are not allowed to break a link, even if you join it back at the end. What if other programs read the list at the same time ?

The algorithm must not damage the list while working on it.