One pass, single Hash Map, 120ms C++ Solution. Let me know if I could improve this speed.


  • 0
    S
    class Solution {
    public:
    	unordered_map<RandomListNode*, RandomListNode*> dict;
    	
    	RandomListNode* copyRandomList(RandomListNode *head) {
    	    if(!head)
    	        return NULL;
    	        
    		RandomListNode* cur = head;
    		RandomListNode* ncur,*nhead = NULL;
    		
    		nhead = new RandomListNode(head->label);
    		dict[cur] = nhead;
    		ncur = nhead;
    		
    		while (cur) {
    			if (cur->random) {
    				if (dict.find(cur->random) == dict.end()) {
    					ncur->random = new RandomListNode(cur->random->label);
    					dict[cur->random] = ncur->random;
    				}
    
    				else
    					ncur->random = dict[cur->random];
    			}
    			if (cur->next) {
    				if (dict.find(cur->next) == dict.end()) {
    					ncur->next = new RandomListNode(cur->next->label);
    					dict[cur->next] = ncur->next;
    				}
    				else
    					ncur->next = dict[cur->next];
    			}
    			ncur = ncur->next;
    			cur = cur->next;
    		}
    
    		return nhead;
    	}
    };
    

Log in to reply
 

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