Spread the post

check palindrome in linked list loop

Write an efficient algorithm to, check palindrome of given linked list loop.

Following steps.

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 check palindrome of this loop.

Example

root_ptr34524321

Result : Not Palindrome

loop value is: [3,4,2,5,4,3] this is not palindrome.

Another example

root_ptr34554321

Result : Palindrome.

loop value is: [3,4,5,5,4,3] this is palindrome.

View nodes and pointers

Stack Areamainroot(pointer)detect_loopfirst_ptr(pointer)second_ptr (pointer) ? status (int) ? 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)= 5next (pointer) struct Nodedata (int)= 4next (pointer) struct Nodedata (int)= 3next (pointer)

Program for check given linked list loop are contain palindrome or not . Time complexity O(n).


Output

Stack Areamainroot(pointer)detect_loopfirst_ptr(pointer)second_ptr(pointer)status (int) =1palindromeend(pointer)start(pointer)status(pointer)palindromeend(pointer)start(pointer)status(pointer)palindromeend(pointer)start(pointer)status(pointer)palindromeend(pointer)start(pointer)status(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)= 5next (pointer) struct Nodedata (int)= 4next (pointer) struct Nodedata (int)= 3next (pointer)

Execution Process Try it Yourself

Spread the post

Recommended Posts: