class Solution {
    public ListNode reverse(ListNode head) {
        ListNode left = null;
        ListNode right = head;
        while (right != null) {
            ListNode newRight = right.next;
            right.next = left;
            left = right;
            right = newRight;
        }
        return left;
    }
    public boolean isPalindrome(ListNode head) {
        if (head == null) return false;
        if (head.next == null) return true;
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null; // 切断
        if (fast != null) { // 链表长度为奇数
            slow = slow.next;
        }
        ListNode p = reverse(slow);
        ListNode q = head;

        while (p != null && q != null) {
            if (p.val != q.val) return false;
            p = p.next;
            q = q.next;
        }
        return true;
    }
}