What is palindrome?

Palindrome is frequently seen in all kinds of computer science textbooks. A palindrome is a word, phrase, number, or other sequence of units that may be read the same way forwards and backwards. The intuitive approach to check if a string or a linked list is a palindrome is to use stack. Stack is a LIFO (Last In First Out) data structure, which perfectly fits to check palindrome.

Implementation

Here provides a simple Java implementation for a linded list:

public static boolean isPalindrome(Node head) {                      
    Stack<Integer> stack = new Stack<Integer>();                     
    Node cursor = head;                                              
    for (cursor = head; cursor != null; cursor = cursor.getLink()) { 
        stack.add(cursor.getData());                                 
    }                                                                
    for (cursor = head; cursor != null; cursor = cursor.getLink()) { 
        if (stack.pop() != cursor.getData()) {                       
            return false;                                            
        }                                                            
    }                                                                
    return true;                                                     
}