/**
* 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;
}
};