class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null){
            return true;
        }

        ListNode pre = new ListNode();
        pre.next = head;
        ListNode faster = pre;
        ListNode slower = pre;
        while(faster != null && faster.next != null ){
            faster = faster.next.next;
            slower = slower.next;
        }
        ListNode mid = slower;

        pre = null;
        ListNode curr = mid.next;
        while(curr != null){
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }

        while( pre != null ){
            if(head.val != pre.val){
                return false;
            }
            head = head.next;
            pre = pre.next;
        }

        return true;
    }
}