C++ (108 ms -- 77%) O(1) space with explanation


  • 0
    J

    You could do this with a hash table (C++ unordered_map), mapping each node to its copy. (One pass to create the copy and populate the hash table, one pass to set the random pointers in the copy.) But there is a time cost to this in the overhead of the hash table (e.g. the hashing function) and it requires extra space.

    This solution works by inserting into the list a copy of each node directly after the node. Once you have this "doubled list" its easy to set the random pointers, and then just as easy to break apart the two lists. No needed space other than what is required for the cloned list.

    RandomListNode *copyRandomList(RandomListNode *head) {
        if (!head)
            return NULL;
            
        RandomListNode* p;
        RandomListNode* q;
        
        // First: "interleave list" -- so each node of the original
        // has a copy following it.
        p = head;
        while (p) {
            q = new RandomListNode(p->label);
            q->next = p->next;
            p->next = q;
            p = q->next;
        }
    
        // Second: set the random points.  For each original node p, we 
        // want to set p->next->random (the copy) to p->random->next (assuming
        // p->random is not NULL).
        p = head;
        while (p) {
            if (p->random) {
                // p->next cannot be null -- as it must be followed by its copy.
                p->next->random = p->random->next;  
            }
            p = p->next->next;
        }
    
        // Now split the two lists.
        RandomListNode* newHead = head->next;
        p = head;
        q = newHead;
        while (p) {
            p->next = q->next;
            q->next = (p->next ? p->next->next : NULL);
            p = p->next;
            q = q->next;
        }
    
        return newHead;
    }

Log in to reply
 

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