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

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 eve开发者_StackOverflown 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.

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.

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

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

Detect loop point By (Slow pointer and fast pointer approach), find the loop detection node

Now take pointers P1 and P2, P1 at the loop detection node and P2 starting from head of the linked list Traverse both the pointers one at a time

Both the pointers meet at the node because of which there is a loop in the linked list

Use the standard fast and slow pointer algorithm find the loop detection point

Take two pointers P1 and P2 at loop detection point. Place pointer P1 at the same place and move P2 forward one step at a time. Repeat until both the pointers meet together. Keep a count variable incremented for every iteration which gives length of the loop. Let say the length is L1

Again take two pointers P1 and P2. P1 at the head of the linked list and P2 at the loop detection point. Forward both the pointers one step at a time. Repeat until both the pointers meet together. This procedure is equivalent to the one we use to calculate node that causes loop in a linked list. Keep a count variable incremented for every iteration which gives the length of the list until the merging point. Let say the length is L2 Now the length of the list that contains loop is L1+ L2

Here's the mathematical justification of the correctness of the popular hare and tortoise algorithm for finding the length of the linked list.

wont it go in infinite loop? if 1 2 3 ... 9 10 form a loop ,which starts at 1.Suppose when pointer from start node reaches 1 ,other pointer is at node 8. then they move as pointer1:- 1 2 3 4 5 .. pointer2:- 8 9 10 1 2.. clearly they wont ever be equal.