Rememer to restore original linked list if it's modified...


  • 0
    C

    Well, I was trying to solve this problem by changing original linked list to a XOR linked list. So no extra space, only side-effect is that original linked list is modified.

    Then I was always getting "Time Limit Exceeded" and have no idea why. I added some printf debug to my code, but everything seemed good and no endless output in the loop. I thought it was a bug of leetcode.

    After trying to simplify my code to illustrate the bug, I noticed that if I don't modify the input linked list then I got expected output. So I simply added some code to restore original linked list, then the code got accepted...

    I think that server might make use of the same linked list to do something, and was stucked because the next pointer is changed...

    Waste a lot of time. Anyway, I think XOR linked list is a good tool to solve this problem with linear time and const space. Here is my code:

    bool isPalindrome(struct ListNode* head) {
        struct ListNode *prev = NULL, *cur = head;
        bool retval = true;
    
        while (cur != NULL) {
            struct ListNode *next = cur->next;
            cur->next = (uintptr_t)prev ^ (uintptr_t)next;
            prev = cur;
            cur = next;
        }
        
        struct ListNode *left_cur = head, *left_prev = NULL;
        struct ListNode *right_cur = prev, *right_prev = NULL;
        
        while (left_cur && right_cur) {
            if (left_cur->val != right_cur->val) {
                retval = false;
                break;
            }
            
            struct ListNode *left_next = (uintptr_t)left_prev ^ (uintptr_t)left_cur->next;
            struct ListNode *right_next = (uintptr_t)right_prev ^ (uintptr_t)right_cur->next;
            
            left_prev = left_cur;
            left_cur = left_next;
            right_prev = right_cur;
            right_cur = right_next;
        }
    
        prev = NULL;
        cur = head;
        while (cur) {
            cur->next = (uintptr_t)prev ^ (uintptr_t)cur->next;
            prev = cur;
            cur = cur->next;
        }
    
        return retval;
    }

Log in to reply
 

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