Many people have the O(n) space solutions, but it does not fulfill the problem request.

This time I'll show you a **truly O(1) space solution** by Java and Python

The key point is XOR arithmetic and the order of the number in the list.By using the XOR you can promise the values in pair exist. And if you add the order(location) to the XOR arithmetic then you can promise the order of the number

Because (for every number a,b) a = a XOR b XOR b. But it can't promise their order.Just like this [1 3 2 3 2 1].So I add the sequence number to "b" to promise their order. As you can see in the code, the value "count" is the seq num and the "m" is the corresponding right one. In this way I can have an intuitive feeling to solve the problem.

But I really know the idea is not perfect because of the function is too easy. So it just a master of time to complete the algorithm.

**//Particularly explain!**

Because the algorithm likes an encryption process. So if you want to construct 2 pairs to decrypt it, of course you can. But it just depends on the encryption function, and here I let the f(x) = x * loc(x). Then you can design a proper f(x) to make up.But this idea(encrypt) is right. Do you think so?

Python Code

```
class Solution:
# @param {ListNode} head
# @return {boolean}
def isPalindrome(self, head):
count = 0
node = head
while head is not None:
count = count + 1
head = head.next
n = count
mid = int(n//2)
isOdd =False
if n < 2:
return True
if n % 2 != 0:
mid = mid + 1
isOdd = True
count = 0
flag = 0
while node is not None:
count = count + 1
if (isOdd and count == mid):
node = node.next
continue
if count > mid:
m = n - count + 1
flag = flag ^ (node.val * m)
else:
flag = flag ^ (node.val * count)
node = node.next
if flag == 0:
return True
else:
return False
```

Java Code

```
public class Solution {
public boolean isPalindrome(ListNode head) {
int count = 0, flag = 0;
ListNode node = head;
while (head != null){
count++;
head = head.next;
}
int n = count, mid = n / 2;
Boolean isOdd = false;
if (n < 2) return true;
if (n % 2 != 0){
mid++;
isOdd = true;
}
count = 0;
while (node != null){
count++;
if (isOdd && count == mid){
node = node.next;
continue;
}
if (count > mid){
int m = n - count + 1;
flag = flag ^ (node.val * m);
}else{
flag = flag ^ (node.val * count);
}
node = node.next;
}
if (flag == 0){
return true;
}else{
return false;
}
}
}
```