Questions on palindrome, anagrams are very common in coding interviews and also very easy to solve if you have solved them before. There are a lot of methods to check If a string or a number is a palindrome or not. In this post, we will use the second method i.e pointers
First Approach: Using Stack
In this method we iterate over the string and for each character we compare the current character is same as that of character at the stack top if yes then we pop the element from the stack top else we push the current character onto the stack, after iterating over the string if the stack is empty then we can declare that the given string is a palindrome else the given string is not a palindrome.
IMP: If the length of the string is odd then we do not push the middle character to the stack.
This method is efficient as we iterate through the linked list only once but it uses extra space in form of a stack.
Algorithm:
- Create an empty Stack
- Push the head node onto the stack
- While the last node of the linked list is not reached do the following actions
- If the contents of the current node and the node at the stack top are same then pop the element from the stack
- else push the current node on the stack
- If we have traversed through the Linked List and the stack is empty then we Return that the String is a palindrome.
In this method, we use 2 pointers left and right and we recursively traverse the linked list. In this method right node points to the tail of the linked list and left node will point to the head of the linked list and if the characters are same at both the node then we move left node forward and right node backward recursively. We return the result in each recursive call.
Algorithm:
- Initialize right and left pointers to head node, make left node as static node pointer
- Move the right node to the end of the linked list recursively
- As soon as the right node reaches the end of the linked list do the following actions
- Compare the data field of left and right nodes if they are same then move the left node forward and return true
C++ Program
Sample input and output to check the program
You might also be interested in
Comments
Post a Comment