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

just remenber where have you been and if you came at same node it is over.

Try storing entries in binary tree and you have O(N*log(N)) time and O(N) space comlexity

EDIT

You can use Log(N) space comlexity if you do not store every but in exponetial order link. That mean that you store 1st, 2nd, 4th, 8th, 16th and then if you get hit you have to continue from that point. Time comlexity for this one is N*Log(n)^2

Answer 2

Check out this: Puzzle: Loop in a Linked List

Pointer Marking: In practice, linked lists are implemented using C structs with at least a pointer; such a struct in C shall be 4-byte aligned. So the least significant two bits are zeros. While traversing the list, you may ‘mark’ a pointer as traversed by flipping the least significant bit. A second traversal is for clearing these bits.

Answer 3

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

Answer 4

The most elegant solution is Floyd's cycle-finding algorithm: http://en.wikipedia.org/wiki/Cycle%5Fdetection#Tortoise%5Fand%5Fhare

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