One pass solution using two hashmaps. Improvement will be appreciated.


  • 0
    H

    My code was accepted but only beat 3% of submissions. Any improvement or suggestions will be appreciated.

    public RandomListNode copyRandomList(RandomListNode head) {
            if(head == null) return null;
            RandomListNode cur = head;
            RandomListNode copyDummy = new RandomListNode(0);
            RandomListNode preCopy = copyDummy;
            /* Used to store nodes each of which is another node's random node. 
              Key is original node and Value is corresponding copied node. 
              A pair in this map means that the node has already been created, 
              although the node could be created in advance. 
              For example, 2 is the second node and 2.random = 4, 
              so when the second node in the original list is being visited, 
              the 4th node in the copy list is created and 
              because that 4th node is 2nd node's random node, 
              we should do randomMap.put(4th original node, 4th copied node). */
            HashMap<RandomListNode, RandomListNode> randomMap = new HashMap<RandomListNode, RandomListNode>();
            // Used to store visited nodes
            HashMap<RandomListNode, RandomListNode> visitedMap = new HashMap<RandomListNode, RandomListNode>();
            
            while(cur != null) {
                RandomListNode copy = null;
                if(!randomMap.containsKey(cur)) { 
                    copy = new RandomListNode(cur.label);
                    preCopy.next = copy;  
                } else {
                    preCopy.next = randomMap.get(cur);
                    copy = preCopy.next;
                }
                
                visitedMap.put(cur, copy);
                
                if(cur.random != null) {
                    if(!visitedMap.containsKey(cur.random)) {
                        RandomListNode randomC = new RandomListNode(cur.random.label);
                        copy.random = randomC;
                    } else {
                        copy.random = visitedMap.get(cur.random);
                    }
                    randomMap.put(cur.random, copy.random);
                }
                cur = cur.next;
                preCopy = preCopy.next;
            }
            
            return copyDummy.next;
            
    }
    

  • 0
    S

    I used a single hash map.

    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.