class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null && head.next==null)
return true;
ListNode middle=findmiddle(head);
ListNode sechalfstart=reversehalf(middle.next);
ListNode firsthalfstart=head;
while(sechalfstart!=null){
if(firsthalfstart.val!=sechalfstart.val)
return false;
firsthalfstart=firsthalfstart.next;
sechalfstart=sechalfstart.next;
}
return true;
}
public ListNode reversehalf(ListNode middle){
ListNode prev=null;
ListNode curr=middle;
while(curr!=null){
ListNode nxt=curr.next;

        curr.next=prev;
        prev=curr;
        curr=nxt;
    }
    middle=prev;
    return middle;
}

public ListNode findmiddle(ListNode head){
    ListNode slow=head;
    ListNode fast=head;
    while(fast.next!=null && fast.next.next!=null){
        slow=slow.next;
        fast=fast.next.next;
    }
    return slow;       
}

}