/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        ListNode * newhead = new ListNode(0),*head2 = NULL;
        newhead->next = NULL;
        ListNode *slow = head,*fast = head->next;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        //偶数个
        head2 = slow->next;
        while(head && head != head2){
            ListNode *temp = newhead->next;
            newhead->next = head;
            ListNode* cur = head->next;
            head->next = temp;
            head = cur;
        }
        if(fast == NULL)
            newhead = newhead->next;
        while(head2){
            if(newhead->next->val != head2->val)
                return false;
            head2 = head2->next;
            newhead = newhead->next;
        }
        return true;
    }
};