a graceful solution than half reverse list


  • 0
    R

    Acutally the problem can be solved using xor(node->prev, node->next).

    1. update "list->next" using xor
    2. compare elements from two sides for the list
    3. restore list, if required

    The drawback of this solution is it works only for C/C++ programming language.

    Piece of code are shown as following, it could be optimized in step #2 by breaking out in half way

    bool check(List* list)
    {
        bool ret = true;
    
        //
        // update all pointers, using XOR
        //
        Node *prev = nullptr;
        auto cur = list->head.next;
    
        while (cur) {
            auto next = cur->next;
            cur->next = xor_pointer(prev, next);
            prev = cur;
            cur = next;
        }
    
        //
        // visit list from head and tail at same time
        //
        Node *head_prev = nullptr, *head = list->head.next;
        Node *tail_prev = nullptr, *tail = prev;
        Node *tmp = nullptr;
    
        while (head && tail) {
            if (head->i != tail->i) {
                ret = false;
            }
            tmp = xor_pointer(head_prev, head->next);
            head_prev = head;
            head = tmp;
    
            tmp = xor_pointer(tail_prev, tail->next);
            tail_prev = tail;
            tail = tmp;
        }
    
        //
        // restore this list
        //
        prev = nullptr;
        cur = list->head.next;
    
        while (cur) {
            cur->next = xor_pointer(prev, cur->next);
            prev = cur;
            cur = cur->next;
        }
    
        return ret;
    }
    

Log in to reply
 

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