How to check whether linked list is palindrome or not?

What is Single Linked List?

 Linked list a data structure used for storing collection of data. It has following properties: 

• Successive elements are connected through reference(Pointer)
• Last Element stores NULL reference.
• Size is not fixed. Can dynamically grow.
• Only Forward traversing is possible, No Backward processing is allowed.
•  No wastage of memory. 

Sample Linked List Class

So far We got basic information about Linked List. 
Now we have to check whether given Linked List is palindrome or not?

Before solving the problem, lets first understand, what is palindrome?. A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward



We can solve this problem by following approaches:

1. Using Stack(Iterative way or Recursive Way(internally uses stack))
1. Push all the elements into stack.
2. Pop the element from stack and compare with header of Linked List
3. If both the elements are same, then header to next node
4. Repeat the steps 2 & 3, until stack is empty and no more left in Linked List  
2.  Without stack
1. First find the middle node of the node.
2. Reverse the second half.
3. Now compare Next pointer of middle with header, 
4. If both are same then move to next pointer and compare. 
5. Repeat step 2 &3 until it reaches to end of the linked list,

LinkList Class


public class LinkList<T> {
    public LinkList() {
    }

    public LinkList(T data) {
        this.data = data;
    }
    private T data;
    private LinkList<T> next;

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public LinkList<T> getNext() {
        return next;
    }
    public void setNext(LinkList<T> next) {
        this.next = next;
    }
}



With Stack:

        Recursive Way:

        
         LinkList<Integer> originalListHeader=getLinkedList();
       
         boolean isPalindrome=isPalindromeRecursiveWay(originalListHeader);

         private boolean isPalindromeRecursiveWay(LinkList<Integer> listHeader) {
                 if (listHeader == null) {
                            return true;
                  }
               if(isPalindromeRecursiveWay(listHeader.getNext())){
                        if(listHeader.getData()==originalListHeader.getData()){
                              originalListHeader=originalListHeader.getNext();
                             return true;
                         }
                       return false;
                 }
        return false;
    }


Iterative Way:  


private boolean isPalindromeIterativeWay(LinkList<Integer> listHeader) {
      Stack<LinkList<Integer>> stack=new Stack<LinkList<Integer>>();
      LinkList<Integer> list=listHeader;
     while(list!=null){
          stack.push(list);
          list=list.getNext();
       } 
    while(listHeader!=null){
          LinkList<Integer> list=stack.pop();
          if(list.getData()!=listHeader.getData()){
                return false;
          }    
         listHeader=listHeader.getNext();
     }
return true;
}




Without Stack:

private boolean isPalindrome1(LinkList<Integer> root) {
        LinkList<Integer> middleNode = middleNode(root);
        LinkList<Integer> middleNext = reverse(middleNode.getNext());
       
        while (middleNext!=null) {
            if (root.getData() != middleNext.getData()) {
                return false;
            }
            root = root.getNext();
            middleNext = middleNext.getNext();
        }
        return true;
    } 

I'll post Middle Node and reverse function in separate post.