How to find the length of a linked list that is having cycles in it?

Question

This was one of the interview questions asked. How to find the length of a linked list that is having cycle in it. I know how to calculate whether a linked list has a cycle or not using Hare and Tortoise technique. I even know how to calculate the length by storing the addresses in a hashset. The running time of the Algorithm should be O(n).

But what I was not able to tell is how to calculate the length of the linked list without using a external space of O(n). Please help me. Thank you.

Answer 1

Once you've detected the cycle, you need to calculate the length of the cycle, and the position at which it starts. The sum of these is the total number of distinct nodes in the list. Details for example here: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

Answer 2

I think If some how you know the starting node of cycle , you can know the length of cycle and hence the total number of nodes in linked list.

For getting starting point you need only O(1) space.

Suppose your two pointers,fast and slow met at 'node t'.

increment one pointer to point to next node. and the other pointer to start of linked list. Now increment both the pointers until they meet.

The meeting point is starting node of cycle.

From this you can get the Length of cycle by traversing again since you know the starting point of cycle.

Answer 3

1. Apply Tortoise and Hare algorithm and stop when characters meet
2. Continue iterating through the list only with Tortoise and reverse each link it will pass

The number of reversed links is the length of the cycle