MCN Professionals | Interview Question of the day
To receive one interview question in your mailbox daily, please subscribe to "A Question A Day" at MCN Professionals home page.-----------------------------------------------------------------------------------------------------------------------------------------
Today's Question:
Write a function to check if a Singly linked list is a palindrome or not. For example, the linked list
2->3->4->5->4->3->2 is a palindrome
M->A->L->A->Y->A->L->A->M is a palindrome
2->3->4->5->4->6->2 is NOT a palindrome
K->A->M->A->L is NOT a palindrome
The function should take O(n) time in worst case.
Solution:
Method-1: Use Recursion
You need to compare the first and last node in the first loop and then compress the list
bool isPalindrome(Node* head)
{
return isPalindromeRec(&head, head);
}
bool isPalindromeRec(Node **l, Node *r)
{
if (!r) // terminating condition
return true;
// If the sublist is not palindrome then don't need to check further
if (! isPalindromeRec(l, r->link) )
return false;
bool flag = (r->data == (*l)->data);
*l = (*l)->link; // Move l forward
return flag;
}
Method-2: Use reverse method - Move to the middle of the list.
- Reverse the second half
- compare the first and reversed second half one node at a time, if the are same return true else false.
- Reverse the 2nd half again to get the original list.
Time Complexity: O(n)
Extra Space used: O(1)
-----------------------------------------------------------------------------------------
Interview Questions Archive:
To see all the questions in the category click
here...