# If you want O(n) time and O(1) space, this problem should not be an 'easy' one.

• For an O(n)-O(1) answer, the common idea can be summarized as:

1. find the middle.
2. reverse half of the list (reverse the latter half would be more comprehensible).
3. easily check for palindromic-ness as if it's a double-link list.
4. restore the reversed half
``````class Solution {
``````

public:
ListNode *node1, *node2, *node3;
node2 = node1->next;
node1->next = NULL;
while(node2)
{
node3 = node2->next;
node2->next = node1;
node1 = node2;
node2 = node3;
}
}

``````bool isPalindrome(ListNode* head) {

// lengths 0, 1 are palindrome
{
return true;
}

// length 2 goes simple judging
{
}

// step 1: find middle and tail nodes
ListNode *middle, *rbegin;
while(rbegin->next)
{
if(rbegin->next->next)
{
middle = middle->next;
rbegin = rbegin->next->next;
}
else
{
rbegin = rbegin->next;
}
}

// step 2: reverse the latter half
reverse(middle->next);

// step 3: check for palindrome
bool result = true;
ListNode* node2 = rbegin;
while(node2)
{
if(node1->val != node2->val)
{
result = false;
break;
}

node1 = node1->next;
node2 = node2->next;
}

// step 4: restore the reversed latter half
reverse(rbegin);

return result;
}
``````

};

• ``````class Solution {
public:
return true;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
ListNode *second = reverseList(fast);
while (second && second->val == head->val) {
second = second->next;
}
slow->next = fast;
return second == NULL;
}
private:
ListNode *pre = NULL, *next = NULL;
}
return pre;
}
};``````

• I reversed the first half except head, which is very convenient in my opinion. below is my code. len/2-2 node(s) been modified and restored.

``````class Solution {
public:
int len=1;
for(;r->next;r=r->next) { ++len; }
// reverse the first half except head, only if len>=6
int i=len/2-2;
ListNode *ml,*mr, *p,*q;
for(;i>0;--i) {
r=q->next;
q->next=p;
p=q;
q=r;
}
// record the boundaries in the middle
ml=p;
mr=q;
// adjust the start pos of second half
if(len&1) q=q->next;
// palindrome check
i=len/2-1;
int isok=1;
for(;i>0;--i) {
if(p->val!=q->val) { isok=0; break; }
p=p->next, q=q->next;
}
// restore the reversed half
i=len/2-2;
p=ml, q=mr;
for(;i>0;--i) {
r=p->next;
p->next=q;
q=p;
p=r;

}
return isok;
}
};``````

• ``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
return true;
while(fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
slow->next = reverse_list(slow);
slow = slow->next;
while(slow) {
return false;

slow = slow->next;
}
return true;
}
private:
ListNode *reverse_list(ListNode *slow) {
ListNode *prev = slow;
ListNode *cur, *tmp_next = prev->next;
while(tmp_next) {
cur = tmp_next;
tmp_next = cur->next;
cur->next = prev;
prev = cur;
}
slow->next->next = nullptr;
return cur;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.