&#62;...destroyed the performance.<p>Interesting point about APIs. Did you try doing one O(n) pass to dump the list into a secondary format? Just walk the list, creating a new list of your own with the new field and then walk it again to do cycle detection? That's two O(n) walks, still O(n) and should take like an hour to implement. I'm assuming you can get some unique ID for each node from the API, which seems reasonable.<p>Could you give some more insights into the scenarios where you don't know the size of the data? I agree it is an interesting algorithm and I would like to have a better grasp over use cases.<p>&#62;you wouldn't have a linked list to start with<p>In my mind I don't typically turn up linked lists in the wild, just relationships which means graphs and some of them have a structure which maps onto a linked list. I find myself thinking more about the general problem of cycle detection in graphs - a linked list is after all only a special case of a graph. Any relationship-centric data can be scraped and end up with this big pile of data where you want to find cycles.<p>I guess my thinking was colored by the start of the article - "It's a classic interview question: Given a (singly-)linked list, determine whether or not it has a cycle."<p>If the question had said, given an immense linked list or in constant space or without knowing the size, I would have thought differently. If someone gives me a linked list, I assume I have the whole thing.<p>I work with large databases fairly regularly myself. These usually come from some data collection effort (e.g. scraping) and I end up with a pile of data I need to make sense of. In my experience, identifiers are typically a relatively small amount of data compared to the rest. Just as a concrete example, I'm currently forklifting about 4.5M entities in 22GB, with the largest set of identifiers coming out to about 250M. So, with long identifiers that means about 2GB of identifiers for the largest entity class - a relatively easy to deal with number.