> Can we assume that the node has a means by which it > tracks its references? > > My thinking is that I could write a method which > retrieves the number of references to an object. As > I pass down the list I use this method and if there is > more than 2 references (mine + 1 referring node) then > this is a circular list. > > It seems like this is a possible solution in C/C++ but > may not be possible in Java.
Short answer is no. Rest of response points you to where this is said in the problem statement. But it is a great idea. You are given an ordinary linked list (which would not have a reference count) and you cannot write the list (thus cannot update the reference counts). To add a reference count would take O(N) space. The solution to this problem is enlightnening, but it is questions like this about potential solutions that interest me the most. I find this problem integrates a lot of ideas from the course. - jeff parker
