# O(1) space and O(n) time C++ solution

• Idea: reverse the latter half part; compare with the former half part; reverse the latter half part.

Because the test case must delete the linked-list in C++, so the third step (recover the latter half part) is essential. Otherwise, it will form a cycle in the linked-list and result a "Time limit exceeded".

``````bool isPalindrome(ListNode* head) {
size_t n = 0;
while(p) p = p->next, ++n;
if (n == 1 || n == 0) return true;

for(int i = 0; i < n/2; ++i) r = r->next;
if (n % 2 != 0) r = r->next;

//reverse the latter half part
p = r->next;
while(p)
{
ListNode * tmp = p->next;
p->next = r;
r = p;
p = tmp;
}

int index = 0;
ListNode * e = r;
for(index = 0; index < n/2 && p->val == r->val; ++index)
{
p = p->next;
r = r->next;
}
bool res = index == n/2;

//reverse the latter half part again
p = e->next;
e->next = nullptr;
for(index = 0; index < n / 2 - 1; ++index)
{
ListNode * tmp = p->next;
p->next = e;
e = p;
p = tmp;
}
return res;
}``````

• I didn't do the step 3 reverse the latter half but it still AC. The difference with your code is that I assign NULL to the next of the last node of the reversed latter half.

``````bool isPalindrome(ListNode* head) {
return true;
}
int count = 0;
while(temp){
temp = temp->next;
count++;
}
ListNode *l2;
int i=1;
while(i<count/2){
temp = temp->next;
i++;
}
if(count%2==0){
l2 = temp->next;
}
else{
l2 = temp->next->next;
}
ListNode* newnext = NULL;//the first new next is NULL;
while(l2->next){
temp = l2->next;
l2->next = newnext;
newnext = l2;
l2 = temp;
}
l2->next = newnext;
while(l2){