s4553711
7/4/2017 - 2:52 PM

234.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* func(ListNode* head) {
        if (head->next != NULL) {
            ListNode *tail = func(head->next);
            tail->next = head;
            head->next = NULL;
        }
        return head;
    }
    ListNode* reverse_list(ListNode* c) {
        if (c == NULL || c->next == NULL) return c;
        ListNode *n = c;
        while(n->next != NULL) {
            n = n->next;
        }
        func(c);
        return n;
    }
    bool isPalindrome(ListNode* head) {
        if (head == NULL || head->next == NULL ) return true;
        ListNode *p = head, *q = head;
        while(q != NULL) {
            p = p->next;
            q = q->next;
            if (q != NULL) q = q->next;
        }
        p = reverse_list(p);
        while(p != NULL) {
            if (head->val != p->val) {
                return false;
            } else {
                head = head->next;
                p = p->next;
            }
        }
        return true;
    }
};