/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


bool isPalindrome(struct ListNode* head){
    if(!head || !head->next)
        return true;
    
    struct ListNode *fast = head, *slow = head, *L = malloc(sizeof(struct ListNode));
    L->next = NULL;
    while(fast && fast->next) {
        //找中点
        slow = slow->next;
        fast = fast->next->next;

        //同时对前面进行反转（头插法）
        head->next = L->next;
        L->next = head;

        head = slow;
    }

    //slow指向后半部分头结点，head指向前半部分头结点
    if(fast)
        slow = slow->next;
    head = L->next;

    //前半部分和后半部分进行比较
    while(head){
        if(head->val != slow->val)
            return false;
        head = head->next;
        slow = slow->next;
    }
    
    return true;
}