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

• ``````class Solution {
public:
return true;
while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
ListNode* second = reverse(slow->next);
if(fast == nullptr) slow = nullptr;
else slow->next = nullptr;
while(first != nullptr && second != nullptr){
if(first->val != second->val)
return false;
first = first->next;
second = second->next;
}
return true;
}
ListNode* reverse(ListNode* root){
if(root == nullptr||root->next == nullptr) return root;
ListNode* prev = nullptr;
ListNode* cur = root;
ListNode* nxt;
while(cur){
nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
};``````

• I think it's better to recover the list in the end.

``````bool isPalindrome(ListNode* head) {
while(fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
reverse(slow);
ListNode* cur2 = slow->next, *cur1 = head;
bool ret = true;
while(cur2) {
if (cur2->val != cur1->val) {
ret = false;
break;
}
cur1 = cur1->next;
cur2 = cur2->next;
}
reverse(slow);
return ret;
}

void reverse(ListNode* pre) {
if (pre == NULL || pre->next == NULL) return;
ListNode* cur = pre->next->next, *tmp = NULL;
pre->next->next = NULL;
while(cur) {
tmp = cur->next;
cur->next = pre->next;
pre->next = cur;
cur = tmp;
}
}``````

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