# My C++ O(N) time, O(1) space code (reverse the first half of the list, compare, and recover the first half)

• The idea is

1. find the length of the list and then reverse the first half of
the list,
2. compare the reversed first half with the second half
to get the result,
3. reverse the first half again to recover the
list

So the algorithm has O(N) time complexity

``````class Solution {
public:
int i, len =0;
bool res = true;

// calculate the length of the list
while(cur)
{
++len;
cur = cur->next;

}

if(len<=1) return true;
else
{
//reverse the first half of the list
for(i = 0, cur = head, prev = nullptr; i<len/2; ++i)
{
suc = cur->next;
cur->next = prev;
prev = cur;
cur = suc;
}

sHead = len%2 ? suc->next:suc; // sHead is the head of the second half list, for odd length, skip the middle node

// compare
{
}
res = (nullptr == sHead); // update the return value

//reverse the first half of the list again;
cur  =prev;
prev = suc;
for(auto i = 0; i<len/2 ; ++i)
{
suc = cur->next;
cur->next = prev;
prev = cur;
cur = suc;
}

return res;
}
}
};``````

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