Your comments are interesting, it shows just how much my background has colored my thinking and caused me to take for granted situations that other people just don't think of.<p><pre><code>  &#62; Space complexity is the issue for only a subset of problems ...
</code></pre>
Hmm.  I deal on a daily basis with datasets that are several GB in size, and don't regard them as especially large.  If I wanted to find a loop in a linked list, I'd worry about allocating memory to a subsidiary data structure that was subsequently going to be thrown away.  Given that I often don't know the size of the data set, I can't easily create a hash structure, so having a wide selection of algorithms like this immediately to hand gives me a good chance of finding something that will work.<p>My first application of this technique was in an implementation of a variation on the Pollard Rho method of factoring.  In that case it's impossible to create a parallel data structure - the teleporting turtle-type of technique is essential.<p><pre><code>  &#62; my inclination is to go for either the hash table
  &#62; or search tree solution unless I really, really
  &#62; have to implement some special algorithm.
</code></pre>
It seems to me that in most of the cases you're considering you wouldn't have a linked list to start with.  I get the feeling that the situations where one would seriously consider using a linked list as opposed to a hash table or tree search are those situations where you do have to worry about these issues.<p>As usual the answer is really to question why there's a linked list to start with.<p><pre><code>  &#62; How would you ever not know the start state
  &#62; of the mark on each node? It's a field you
  &#62; invented, ...
</code></pre>
Again, not always the case.  I regularly deal with libraries and I'm given an API, but I don't get to define the fields.  This happened to me recently where I had a complex data structure and I wanted a flag on each node, but couldn't have it.  The solution we thought of first built a subsidiary data structure to keep the additional information, but that destroyed the performance.  In the end we used a trick like the teleporting turtle, that reminded me of Floyd's algorithm, and so I wrote it up.