How To Check if a linked list of strings is palindromic

Given a linked list of strings, check whether concatenation of all values in the list together forms a  palindrome. It is not permissible to construct a string out of the linked list nodes and check that string for palindrome.

 
For example,

Input:  AA -> XYZ -> CD -> C -> ZYX -> AA -> null
Output: String AAXYZCDCZYXAA is palindrome
 
Input:  A -> B -> C -> DC -> B -> null
Output: String ABCDCB is not a palindrome
 
The idea is to traverse till the end of the linked list using recursion and construct a string which contains concatenation of all values in the linked list nodes (in encountered order). Then when the recursion unfolds, we construct another string which contains concatenation of all strings in reverse order. This time, the encountered order of linked list nodes is opposite. i.e. from last node towards the head node.
Now the problem reduces to just validating if both constructed strings are equal or not. If both strings are same, we can say that the linked list is palindromic.



Output:

Linked List AA -> XYZ -> CD -> C -> ZYX -> AA -> null is a palindrome.


Learn More :