# An idea - use XOR linked list

• An XOR linked list is a data structure takes advantage of the bitwise XOR operation to decrease storage requirements for doubly linked lists.

We all know that verify a palindrome in doubly linked list is as easy as in an array. By turning the singly linked list into a XOR linked list, we effectively get a doubly linked list with no additional space cost.

This only works for C/C++ which support pointer and don't have garbage collection. The XOR link is not a direct reference to the node, therefore GC may consider those nodes as garbage.

C++

``````class Solution {
public:
ListNode *XOR(ListNode *a, ListNode *b) {
return (ListNode *) ((intptr_t) (a) ^ (intptr_t) (b));
}
/* turn it into a xor linked list */
ListNode *prev = NULL;
int n = 0;
for (ListNode *curr = head; curr != NULL; n++) {
ListNode *next = curr->next;
curr->next = XOR(prev, next);
prev = curr;
curr = next;
}
/* check the palindrome */
ListNode *left = head; ListNode *left_prev = NULL;
ListNode *right = prev; ListNode *right_prev = NULL;
int i = 0;
for (; i < n / 2; ++i) {
if (left->val != right->val) break;
left_prev = XOR(left_prev,left->next);
swap(left_prev, left);
right_prev = XOR(right_prev,right->next);
swap(right_prev, right);
}
/* restore the singly linked list */
prev = NULL;
for (ListNode* curr = head; curr != NULL; curr = curr->next) {
curr->next = XOR(prev, curr->next);
prev = curr;
}
return i >= n / 2;
}
};
``````

• Pretty neat idea. Gets TLE, though, for input `[1,2]`. You `return` without restoring the list, probably messing with the judge's freeing of the nodes.

• yes. change that into `break` and `return i >= n/2` can fix it.
Got ac. it runs in 28 ms.

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