Code pasted

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // find the middle point, [h, p) is the first (smaller) part
        if (not pHead or not pHead->next) return true;
        ListNode *p, *q;
        p = q = pHead;
        while (q && q->next) {
            p = p->next;
            q = q->next->next;
        }

        // reverse the second part
        if (q) p = p->next;
        ListNode *last = nullptr;
        while (p) {
            auto pnxt = p->next;
            p->next = last;
            last = p;
            p = pnxt;
        }

        // is two part the same?
        p = pHead;
        while (last && last->val == p->val) {
            last = last->next;
            p = p->next;
        }

        return last == nullptr;
    }
};