An idea - use XOR linked list


  • 4

    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));
        }
        bool isPalindrome(ListNode *head) {
            /* 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;
        }
    };
    

  • 0

    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.


  • 0

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


Log in to reply
 

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