Spread the post

Length of loop in linked list

Write an efficient algorithm to, find the length of loop in given linked list.

Following steps are given to find the length of loops.

1) First need to detect loop of linked list. use two pointer first_ptr, and second_ptr. this both pointer start with first node of linked list. first_ptr are increment by one (visited next memory block) and second_ptr are increment by 2. If first_ptr are equal to second_ptr that means loop are exist in linked list.do step 2. Otherwise loop are not found.

2) In case loop are found then use one length integer variable and assign the value of 1. visit first_ptr to next node and continue this process until first_ptr not equal to second_ptr.

Example

Detect loop

Result length of loop is : 6.

Given function.

View nodes and pointers

Stack Areamainroot(pointer) Heap Areastruct Nodedata (int)= 1next (pointer) struct Nodedata (int)= 2next (pointer) struct Nodedata (int)= 3next (pointer) struct Nodedata (int)= 4next (pointer) struct Nodedata (int)= 5next (pointer) struct Nodedata (int)= 6next (pointer) struct Nodedata (int)= 7next (pointer) struct Nodedata (int)= 8next (pointer)

Program for find length of loop in linked list . Time complexity O(n).


Output

Stack Areamainroot(pointer)loop_lengthfirst_ptr(pointer)length (int) =6second_ptr(pointer) Heap Areastruct Nodedata (int)= 1next (pointer) struct Nodedata (int)= 2next (pointer) struct Nodedata (int)= 3next (pointer) struct Nodedata (int)= 4next (pointer) struct Nodedata (int)= 5next (pointer) struct Nodedata (int)= 6next (pointer) struct Nodedata (int)= 7next (pointer) struct Nodedata (int)= 8next (pointer)

Execution Process Try it Yourself

Spread the post

Recommended Posts: