My solution would have been: Simply have a wrapper around the linked list that keeps count of the elements (+1 for insert, -1 for delete, initialized with 0).
Traverse the list. If your traversal takes more steps than there are elements, you can stop it and conclude there's a cycle. I wonder how the interviewer would value this answer...
If I was interviewing you, I would point out that you're redefined the question: the question gives you a standard linked list, and you state that you want a wrapper-api around it. I would then ask you to try to find a solution that works for a bare bones linked list.
I would make a note that you did find one type of solution, of course.
edit: I would probably also ask why you created an api that even allows cycles, being as that you are defining control over adding and removing elements. Further, if you stated that your api explicitly allows cycles, I would ask why you don't simply mark them at insertion time and flag them, making the "detection" algorithm O(1).
The naive way to do it is just create a hashset that stores pointer to next, walk the linked list, and if you get a collision you have a cycle. The problem is that it requires O(n) memory, where the tortoise and hare method only needs O(1).
As others noted you can't know how many elements there are supposed to be in the list. But you can guesstimate.
1. Take a guess about how much memory the program has allocated so far. If you can't, go with 2^48 = 281474976710656 bytes - the maximum you can do on a 64bit pc today.
2. Divide by the minimum size of a list entry.
3. Traverse the list until the end or until you traverse more elements than there ever could be.
In general though, as noted, you'll know if you're making a list that could possibly contain cycles due to exposing an interface that allows the creation of cycles. In that case, given that you want to be able to efficiently detect cycles, you'd make a special linked list implementation that does keep internal count of its size.
That's a great idea. I had another approach that assumed the entry addresses were aligned to 32/64 bit words in memory as structure's by default are. Then the next pointers will never have the ones or twos bit place set and can be used as a visited marker[1]. This gives a O(n) with a much smaller constant factor than the hair and tortoise.
If you argued that many programming languages already provide list.size() or equivalent (more so if I told you "in a language of your choice" before), I'd swallow my pride and accept it.
Then I'd suggest you try the other way, but it's a perfectly good answer.
The problem is, in Java and probably many others, that method computes the size in linear time by traversing the list. The javadocs for java.util.LinkedList note that this was a decision taken so that splitting a list at an arbitrary node, etc. could be a constant-time operation.
