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
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;
List => 1 ---> 2 ---> 3 ---> 4 ---> 5 ---> 6 / \ 10 7 \ / 9 <--- 8 OURTPUT => 1 ---> 2 ---> 3 ---> 4 ---> 10 ---> 9 / \ 5 8 \ / 6 <--- 7
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