struct ListNode* FirstListEnd(struct ListNode* head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast->next != NULL && fast->next->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

struct ListNode*reserve(struct ListNode* head)
{
    struct ListNode* pre = NULL;
    struct ListNode* cur = head;
    while(cur != NULL)
    {
        struct ListNode* nextTemp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nextTemp;
    }
    return pre;
}

bool isPalindrome(struct ListNode* head){
    if (head == NULL) {
        return true;
    }

    // 找到前半部分链表的尾节点并反转后半部分链表
    struct ListNode* firstHalfEnd = FirstListEnd(head);
    struct ListNode* secondHalfStart = reserve(firstHalfEnd->next);

    // 判断是否回文
    struct ListNode* p1 = head;
    struct ListNode* p2 = secondHalfStart;
    
    while ( p2 != NULL) {
        if (p1->val != p2->val) {
           return false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    // 还原链表并返回结果
    firstHalfEnd->next = reserve(secondHalfStart);
  
   return true;
}