# How to calculate the length of a Link List if it contains a loop?

4,824 views
How to calculate the length of a Link List if it contains a loop?
posted Oct 28, 2013

Answer may vary for semi and full circular loop.
Is it full circular list ?
what is full circular or semicircular in this particular case.
Full means the end node always points first node. Semi in the sense it can point  any intermediate nodes event last node.
I think it is generic question so loop could be full loop or semi loop thats what I understood the question.
correct salil. But if it is full circular then we can simply the code, that is why I asked.

Anyway fine.
if it is full loop then I think its very simple count the no of nodes from the start to end (end means your second pointer is moving one at a time and start pointer is not changing and where other pointer meet the start pointer is the end of loop)

+1 vote
{
list *ptr1, *ptr2;
static int count = 0;
while(ptr2 && ptr2->next)
{
ptr2 = ptr2->next->next;
ptr1 = ptr1->next ;
count++;
if (ptr1 == ptr2)   /* Now ptr1 and ptr2 will point node "6". */
{
while (ptr2 != ptr1)
{
ptr1 = ptr1->next ;
ptr2 = ptr2->next ;
count++;
}
break;
}
}
return count;
}

Example 1:-
List1
1   2   3   4   5   6   7   4

Ptr1 = Ptr1->next
Ptr2 = Ptr2->next->next
ptr1 ptr2
1    1
2    3
3    5
4    7
5    5

Now Ptr2 = 1  ptr1 = 5
Ptr1 = Ptr1->next & Ptr2 = Ptr2->next

ptr1 ptr2
5    1
6    2
7    3
4    4

4 is the end node
=============================================================
Example 2:-
List2
1   2   3   4   5   6   7   8   4
Ptr1 = Ptr1->next
Ptr2 = Ptr2->next->next

ptr1 ptr2
1   1
2   3
3   5
4   7
5   4
6   6

Now Ptr2 = 1  ptr1 = 6
Ptr1 = Ptr1->next & Ptr2 = Ptr2->next

ptr1 ptr2
6   1
7   2
8   3
4   4

4 is the end node
cross check your algo of count for even and odd size of the loop, in the figure you had 5 elements in the loop see if it has just 4.
Thanks to point out this error :)
You are right. Give me some time I will make it generic.
looks to be chellenging question
No not challenging code was ok.
But I did not get the chance to run it.
It will work for all loops. :)
Similar Questions
List => 1 --->  2 --->  3 --->  4 ---> 5 ---> 6
/        \
10          7
\          /
9 <---  8

OURTPUT => 1 --->  2 --->  3 --->  4 ---> 10 ---> 9
/        \
5           8
\          /
6 <---  7