Count number of nodes in a linked list that may be circular

Question

Here is the problem, it is from Sedgwick's excellent Algorithms in Java (q 3.54)

Given a link to a node in a singly linked list that contains no null links (i.e. each node either links to itself or another node in the list) determine the number of different nodes without modifying any of the nodes and using no more than constant memory space.

How do you do it? scan through the list once using the hare and tortoise algorithm to work out whether it is circular in any way, and then scan through again to work out where the list becomes circular, then scan through again counting the number of nodes to this position? sounds a bit brute-force to me, I guess there is much more elegant solution.

Answer 1

The tortoise and hare algorithm can give you both the cycle length and the number of nodes before the cycle begins (λ and μ respectively).

Answer 2

The most elegant solution is Floyd's cycle-finding algorithm: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

It runs in O(N) time, and only constant amount of memory is required.