/**
knakul853
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {

        ListNode* slow = head;
        ListNode* fast = head;

        while( fast && fast->next )
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        slow = reverse( slow );
        fast =  head;

        while( slow && fast )
        {
            if(slow->val != fast->val )return false;

            slow = slow->next;
            fast = fast->next;
        }

        return true;


    }

    ListNode* reverse( ListNode* head )
    {
        ListNode* pre = NULL;

        while( head )
        {
            //1->2->3
             ListNode* temp = head->next;
            head->next = pre;
            pre = head;
            head = temp;
        }

        return pre;
    }
};