top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+7 votes
530 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 LinkedIn 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

...