top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

How to know the size of the loop (only the loop size) in a single Link List?

+7 votes
145 views
How to know the size of the loop (only the loop size) in a single Link List?
posted Oct 28, 2013 by Salil Agrawal

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button

2 Answers

+1 vote
 
Best answer
int CountNode_LoopList (list *head)
{
    list *ptr1, *ptr2;
    ptr1 = ptr2 = head;
    static int count = 1;
    while(ptr2 && ptr2->next)
    {
        ptr2 = ptr2->next->next;
        ptr1 = ptr1->next ;
        if (ptr1 == ptr2)  
        {
            ptr2 = head;
            while (ptr2 != ptr1)
            {
                ptr1 = ptr1->next ;
                ptr2 = ptr2->next ;
            }
            break;
        }
    }
    ptr1 = ptr2->next;
    while (ptr2 != ptr1)
    {
        count++;
        ptr1 = ptr1->next ;
        ptr2 = ptr2->next ;
    }   
    return count;
}

Length of a Link List if it contains a loop
How to know if linklint has a loop

answer Oct 29, 2013 by Vikas Upadhyay
+1 vote
Step 1: user two pointers (p1 and p2) both are pointing to head. 
             And counter as integer initialized as zero.
Step 2: p1 = p1.next;
              p2 = p2.next.next;

Step 3: while (p1 != p2) 
              {
                      p1=p1.next;
                      p2=p2.next.next;
              }

Step 4: Now calculate the loop size
              p2  = p2.next;
              while (p1 != p2) 
              {
                      p2=p2.next;
                      counter++;
              }

Step 5: return counter;
answer Oct 28, 2013 by Deepankar Dubey
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

List => 1 2 3 4 5 6 7 8 9

N=3 Out Put => 1 2 3 6 5 4 7 8 9
N=4 Out Put => 1 2 6 5 4 3 7 8 9
N=5 Out Put => 1 2 7 6 5 4 3 8 9

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...