Given a singly linked list, determine if it is a palindrome. Write a Boolean function to output true or false based on result
belongs to collection: Interview C++ coding problems/challenges | Linked list
All Answers
total answers (1)
belongs to collection: Interview C++ coding problems/challenges | Linked list
total answers (1)
For a single linked we don't have a prev pointer to traverse back from the end of the list and to check with corresponding start positions, i.e., what we normally do to check a string to be palindrome. But for a single linked list we only can traverse forward.
Algorithm:
1. Declare a global temp variable ListNode* temp; //function which pass head pointer to check whether it's palindrome 2. bool isPalindrome(ListNode* head) temp=head; return checkPalindrome(head); End Function 3. Recursive function : boolcheckPalindrome(ListNode* p) a. Check for base case IF p==NULL return true; b. bool result=checkPalindrome(p->next) &(temp->data==p->data); c. Traverse tempby one step. temp=temp->next; return result; END FUNCTIONAttention here!!!
For any statement like, bool result=checkPalindrome(p->next) &(temp->data==p->data);
Where there is two expression linked with ‘&' or ‘&&' operator the first expression is evaluated first and in case if it's true, only the second expression is evaluated. If the first expression is false, second expression is not at all evaluated.
So for this particular statement,
checkPalindrome(p->next) is kept being evaluated until recursion reaches the base case & (temp->data==p->data) is not at all evaluated until the first expression results true .
Let's evaluate how the function works to check whether it's a palindrome.
For example 2:
C++ implementation
Output
need an explanation for this answer? contact us directly to get an explanation for this answer