Given a singly linked list, determine if it is a palindrome. in O(1) time and O(1)space   Constraint: Explicit space not allowed (Hint :Use Recursion Stack)

Sample Test Cases:

1. Input: 1->2
   Output: false


2. Input: 1->2->2->1
   Output: true

Answer:

                        
                            /**
                            * Definition for singly-linked list.
                            * public class ListNode {
                            *     int val;
                            *     ListNode next;
                            *     ListNode(int x) { val = x; }
                            * }
                            */
                           class Solution {
                               public boolean isPalindrome(ListNode head) {
                                   if(head==null)
                                   {
                                       return true;
                                   }
                                   ListNode temp=head;
                                   ListNode node=isPalindrome(head, temp);
                                   if(node!=null)
                                       return true;
                                   else
                                       return false;
                               }
                               public ListNode isPalindrome(ListNode head, ListNode rHead)
                               {
                                   if(head==null)
                                   {
                                          
                                       return rHead;
                                   }
                                   ListNode head1=isPalindrome(head.next, rHead);
                                    
                                 
                                   if(head1==null)
                                   {
                                       return null;
                                   }
                                if(head1.val==head.val)
                                   {
                                       if(head.equals(rHead))
                                       {
                                           
                                           return rHead;
                                       }
                                       return head1.next;
                                   }
                                   else
                                   {
                                       
                                       
                                       return null ;
                                   }
                               }
                           }