> Did you try doing one O(n) pass to dump the > list into a secondary format? In this case it wasn't a list, and there was the problem of knowing if I'd alre

> Did you try doing one O(n) pass to dump the > list into a secondary format? In this case it wasn't a list, and there was the problem of knowing if I'd already walked the entire structure, because there may have been loops, and it's the entire loop detection problem all over again. That was one problem with trying to build the subsidiary structure. We had to do it lazily, and, oh, it's too complex to try to obfuscate what we were doing, and I can't tell you the details because it's commercial in confidence. Sorry. I should add that a lot of my contexts are semi-embedded systems, so limitations in memory, disk, CPU and bandwidths are all unsual. > Could you give some more insights into the scenarios > where you don't know the size of the data? Sadly, no, sorry. In some sense the original problem really encapsulates the essence. Your ideas are valid in many, perhaps virtually all cases, but sometimes you need to solve the problem as given without finding tricks to get around them. I come across problems like that, which is why I like to have a wide range of techniques. > 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." Noted - I'll look at putting a side note to put it into the more general context to help avoid putting people's thoughts into a smaller box. Thank you.