I could definitely be mistaken, but I don't see a difference between a linked list and a graph. They are two ways to represent the same thing. That being said, if he asked me to find cycles in a linked list, I might determine the adjacency matrix and check for loops:
"I could definitely be mistaken, but I don't see a difference between a linked list and a graph."
A linked list is a particular type of DAG (or at least DG). The relevant distinction between linked list and the general case is that a linked list restricts nodes to (zero or) one outbound edge. This is relevant to the problem at hand, because you only have one tortoise and one hare and so they can only follow one path.
Right. As a graph theorist might put it, a linked list is a directed graph with a vertex-disjoint path cover consisting of exactly one path. I.e., linked lists are specialized graphs. The tortoise-and-hare algorithm can be generalized to detect cycles in any connected graph, as long as a consistent traversal order is used.
I think it depends on how the graph is represented. With the "standard" representations, it would be O(n) space in the worst case, where n is the number of nodes in the graph. You'd still only need the 2 pointers, but the traversal itself would need to also remember which paths it has not yet visited. The worst case is when the number of paths is much larger than the length of any particular path. The best case (apart from the null graph) is equivalent to the linked list, where there is only one path in the cover.
I can imagine representing the graph as a list of paths, in which case the tortoise-and-hare algorithm is O(1) space, though the graph itself would be (potentially much) larger. Virtually every other operation on such a graph would take a performance hit, too.
There may be other factors I haven't thought of, but you're right that the generalized algorithm could not be as space-efficient as the special algorithm.
It's worth noting, though, that the original question poised in the article did not place an O(1) restriction on space.
Ok, that was poorly worded. What I mean is that a linked list can be thought of as a restrictive graph. I'm just saying I'd prefer to think of it as a graph. I could still be wrong. Is that kosher?
That's certainly kosher (though, nitpicking terminology, I'd say "restricted" rather than "restrictive").
That doesn't get around the original objection, though, which is that the restriction has to be exploited to get the algorithm in question, and thus the algorithm cannot be applied to the general case of graphs.
Having said that, certainly the ability to make use of restrictions provided by your domain is hugely valuable, and this should serve as a relatively familiar case.
http://stackoverflow.com/questions/16436165/detecting-cycles...
This is at least very easy to reason about. However, if you are still right my thought process is just very wrong.