Here is what i did, cost 334mm.. what does it differ from yours?


  • 0
    L
    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
    		 if (!head) return head;
    		 unordered_map<RandomListNode*, RandomListNode*> m;
    		 RandomListNode* q = head;
    		 RandomListNode* p = new RandomListNode(head->label);
    		 RandomListNode* newHead = p;
    		 m.insert(make_pair(q, p));
    		 while (q->next)
    		 {
    			 p->next = new RandomListNode(q->next->label);
    			 m.insert(make_pair(q->next, p->next));
    			 q = q->next;
    			 p = p->next;
    		 }
    		 p = newHead;
    		 q = head;
    		 while (q)
    		 {
    			 RandomListNode* tmp = q->random;
    			 if (tmp)
    			 {
    				 auto it = m.find(q->random);
    				 if (it != m.end())
    				 {
    					 p->random = it->second;
    				 }
    			 }
    			 q = q->next;
    			 p = p->next;
    		 }
    		 return newHead;
    	 }
    };

  • 0
    W

    unordered_map is a good idea. I donot know why hash_map is invalid. 312ms

    class Solution {
    public:
    unordered_map<RandomListNode*, RandomListNode*> nodelist;
    RandomListNode *output;

    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head==NULL)
        {
            return NULL;
        }
        
        return iter(head);
    }
    
    RandomListNode* iter(RandomListNode *head)
    {
        if (head==NULL)
        {
            return NULL;
        }
        auto it = nodelist.find(head);
        if (it != nodelist.end())
        {
            return it->second;
        }
        
        RandomListNode *temp = new RandomListNode(head->label);
        nodelist.insert(make_pair(head, temp));
        
        temp->next = iter(head->next);
        temp->random = iter(head->random);
        
        return temp;
    }
    

    };


Log in to reply
 

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