top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+8 votes
10,783 views
How to calculate the length of a Link List if it contains a loop?
posted Oct 28, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
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 Answer

+1 vote
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;
}

Loop in List

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
answer Oct 28, 2013 by Vikas Upadhyay
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
+4 votes
List => 1 --->  2 --->  3 --->  4 ---> 5 ---> 6
                                      /        \
                                    10          7
                                     \          /
                                      9 <---  8


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

A list contains a set of numbers, one number presents once and other numbers present even no. of times. Find out the number that occurs once in the list.

+3 votes

Want to write the code in C to detect a loop in the link-list, please help.

+3 votes

Is it possible if yes can someone share the code in C?

...