How to determine whether a linked list contains a loop? [duplicate]

This question already has answers here: Closed 12 years ago.

Possible Duplicates:

find whether a loop in a linked list without two pointers

How to determine if a linked list has a cycle using only two memory locations.

Best algorithm to test if a linked list has a cycle

During a preparation for a job interview, I encountered the following question:

How can you determine whether a linked list (of any type) contains a loop, using additional space complexity of O(1)? You cannot assume that the loop starts at the first node (and of course, the loop doesn't have to contain all node开发者_运维百科s).

I couldn't find the answer, though I have the feeling it's quite simple...

---

Easy. Maintain two pointers into the list. At each step, advance one pointer by a single link, and advance the other by two links. Test to see if they point to the same element. If so, you have a loop. If not, repeat until you find a loop or you reach the end of the list.

---

Probably the same technique as checking if a graph is a tree (trees don't get to have cycles), see this this question. It recommends either a topological sort or a depth first search.

---

I had this exact problem in real live code last week.

All I did was kept a pointer (link) for the first element. Then as I iterated through the list, if I ever got that pointer again, I know there's a loop.