palindromeLinkedList.java

/*Please note that it's Function problem i.e.
you need to write your solution in the form of Function(s) only.
Driver Code to call/invoke your function is mentioned above.*/

/* Structure of class Node is
class Node
{
	int data;
	Node next;
	
	Node(int d)
	{
		data = d;
		next = null;
	}
}*/
class GfG
{
    boolean isPalindrome(Node head) 
    {
        if(head == null|| head.next == null)
        return true;
        Node slow = head;
        Node fast = head;
        Stack<Integer> st = new Stack<Integer>();
        while(fast !=null && fast.next != null){
            st.push(slow.data);
            fast =fast.next.next;
            slow = slow.next;
        }
        if(fast !=null )            // odd number
            slow = slow.next;
        while(slow != null){
            if(slow.data != st.pop())
                return false;
            slow = slow.next;

        }
        return true;
        
    }    
}