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

Question

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


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

Answer 1

int CountNode_LoopList (list *head)
{
    list *ptr1, *ptr2;
    ptr1 = ptr2 = head;
    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". */
        {
            ptr2 = head;
            while (ptr2 != ptr1)
            {
               ptr1 = ptr1->next ;
               ptr2 = ptr2->next ;
                   count++;
            }
            break;
         }
    }
    return count;
}

http://tech.queryhome.com/17885/how-to-know-if-linklint-has-a-loop#.Um31gRBRooM

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

Comments

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. :)