Check if Linked List is Palindrome Geeks solution

Check if Linked List is Palindrome Geeks solution

  July 22, 2017    

---

Problem :

write a function which returns true if the given list is palindrome, else returns false.

Ex : 
A list having data
1 2 3 2 1 is palindrome 

Idea 

STL of linkedlist is being created by traversing each node.
Call function which removes first and last element of LL and check whether they are equal or not.

Code:

/* Structure of class Node is
class Node
{
int data;
Node next;

Node(int d)
{
data = d;
next = null;
}
}*/
class hackerranksolutionc
{
    boolean isPalindrome(Node head) 
    {
        int count=0;
        LinkedList<Integer> q=new LinkedList<Integer>();
        while(head!=null)
        {
            q.add(head.data);
            head=head.next;
            count++;
        }
        while(q.size()>1)
        {
            if(q.removeFirst()!=q.removeLast())
            return false;
        }
        return true;
    }    

}

Code using recursion (More Optimized)

boolean isPalindromeUtil(Node right) 
    {
        left = head;
         
        /* stop recursion when you are at last node */
        if (right == null)
            return true;

        /* If sub-list is not palindrome then no need to
           check for current left and right, return false */
        boolean isp = isPalindromeUtil(right.next);
        if (isp == false)
            return false;

        /* Check values at current left and right */
        boolean isp1 = (right.data == left.data);

        /* Move left to next node */
        left = left.next;

        return isp1;
    }