class Result{
        public Result(ListNode node, boolean result){
            this.result = result;
            this.node = node;
        }
        public boolean result;
        public ListNode node;
    }

    private int getListLength(ListNode node){
        int count = 0;
        while(node != null){
            count++;
            node = node.next;
        }
        return count;
    }

    public boolean isPalindrome(ListNode head){
        int length = getListLength(head);
        Result res = isPalindromRecursive(head, length);
        return res.result;
    }

    public Result isPalindromRecursive(ListNode head, int length){
        //we reached the end of the first return nth element
        if(head == null || length <= 0)
            return new Result(head, true);
        //the number of nodes in odd, return the next element
        if(length == 1)
            return new Result(head.next, true);

        Result res = isPalindromRecursive(head.next, length - 2);
        if(!res.result || res.node == null){
            return res;
        }

        res.result = head.val == res.node.val;
        res.node = res.node.next;;

        return res;
    }
}