Find length of loop in a linked list
Given a linked list, write a program that checks whether the given Linked List contains a loop or not and if the loop is present then return the count of nodes in the loop or else return 0. (this is mainly a functional problem).
Loop in the linked list
There is a loop in the above linked list.
As, 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 3 → 4 → 5 → 6 → 7 → 8 → 3...so on.
Thus, there is a loop between 3 and 8 and the length of loop is 6.
The above problem has two sections:
We declare two pointers: one slow pointer and another fast pointer. The slow pointer moves slowly, only one step at each iteration. The fast pointer moves fast, two steps at each iteration. Slow pointer and fast pointer are initially set to the head & head->next respectively.
If there is a loop then the fast pointer and slow pointer will point to a similar node after finite no of iteration
The fast pointer will reach NULL.
Let’s solve the above example using this algorithm...
In case there’s no loop, let’s consider these case too...
Such an example is any single linked list terminated by NULL, 1 → 2 → 3 → 4 → 5 → 6 → NULL
In this case the fast pointer reaches the NULL fast and the program terminates detecting no loop.
Finding length of loop
C++ Implementation to find length of loop in a linked list
Outputneed an explanation for this answer? contact us directly to get an explanation for this answer