Copy List with Random Pointer (C++): Time Limit Exceeded - why??


  • 0
    N
    RandomListNode *copyRandomList(RandomListNode *head)
    {
        if(NULL == head)
            return NULL;
     
        map<RandomListNode*, RandomListNode*> connections;
        RandomListNode *copyHead = new RandomListNode(head->label);
        RandomListNode *curr = copyHead;
    
        // add to map
        connections.insert(make_pair(curr, head));
        
        head = head->next;
        
        while(head)
        {
            curr->next = new RandomListNode(head->label);
            curr = curr->next;
            
            // add to map
            connections.insert(make_pair(curr, head));
            
            head = head->next;
        }
        
        curr = copyHead;
        
        while(curr)
        {
            map<RandomListNode*, RandomListNode*>::iterator it;
            
            it = connections.find(curr);
            
            RandomListNode *temp = it->second;
            
            for(it = connections.begin(); it!= connections.end(); it++)
            {
                    if(temp->random == it->second)
                    {
                        curr->random = (RandomListNode*)it->first;
                        break;
                    }
            }
            curr = curr->next;
        }
        
        return copyHead;
    }

  • 0

    Actually the inside "for" loop is not necessary~
    Your solution has the complexity of O(n*n). The better solution can be O(2 * n).


Log in to reply
 

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