Given a singly linked list, determine if it is a palindrome.

Solution: 先找中点，再翻转后一半，再比较两个list是否一样。注意奇数/偶数个node的不同(可用findMiddle的fast判断奇偶）

    class Wrap{
        ListNode middle;
        boolean isEven;
        public Wrap(){
            middle = null;
            isEven = false;
        }
    } 

    public boolean isPalindrome(ListNode head) {
        // Write your code here
        if(head == null || head.next == null){
            return true;
        }
        Wrap result = findMiddle(head);
        ListNode h1 = result.middle.next;
        ListNode h2;
        if(result.isEven){
            h2 = reverse(head, result.middle.next);
        } else{
            h2 = reverse(head, result.middle);
        }

        return checkIsSame(h1, h2);
    }
    private Wrap findMiddle(ListNode head){
        if(head == null){
            return new Wrap();
        }
        ListNode slow = head, fast = head.next;
        Wrap result = new Wrap();
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        result.middle = slow;
        if(fast != null){
            result.isEven = true;
        } else{
            result.isEven = false;
        }
        return result;
    }
    private ListNode reverse(ListNode head, ListNode tail){
        if(head == null){
            return head;
        }
        ListNode prev = null, curt = head;
        while(curt != tail){
            ListNode temp = curt.next;
            curt.next = prev;
            prev = curt;
            curt = temp;
        }
        return prev;
    }
    private boolean checkIsSame(ListNode h1, ListNode h2){
        while(h1 != null && h2 != null){
            if(h1.val != h2.val){
                return false;
            }
            h1 = h1.next;
            h2 = h2.next;
        }
        if(h1 != null || h2 != null){
            return false;
        } else{
            return true;
        }
    }