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.
