class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;  // 如果链表为空，则认为是回文
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;  // p1指针从链表头开始
        ListNode p2 = secondHalfStart;  // p2指针从反转后的后半部分开始
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;  // 一旦发现值不相同，设置result为false
            }
            p1 = p1.next;  // p1前进到下一个节点
            p2 = p2.next;  // p2前进到下一个节点
        }        

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);  // 将后半部分重新反转回原来的顺序
        return result;  // 返回是否为回文的结果
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;  // 用于记录前一个节点
        ListNode curr = head;  // 当前遍历到的节点
        while (curr != null) {
            ListNode nextTemp = curr.next;  // 临时存储当前节点的下一个节点
            curr.next = prev;  // 将当前节点的next指针指向前一个节点，实现反转
            prev = curr;  // 更新prev为当前节点
            curr = nextTemp;  // 移动curr到下一个节点
        }
        return prev;  // 返回反转后的头节点，即原链表的尾节点
    }

    // 使用快慢指针寻找链表的中间节点
    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;  // 快指针，每次移动两步
        ListNode slow = head;  // 慢指针，每次移动一步
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;  // 快指针前进两步
            slow = slow.next;  // 慢指针前进一步
        }
        return slow;  // 当快指针到达链表尾部时，慢指针刚好在中间
    }
}