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

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

``````public RandomListNode copyRandomList(RandomListNode 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;

}
``````

• I used a single hash map.

``````class Solution {
public:
unordered_map<RandomListNode*, RandomListNode*> dict;

return NULL;

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;
}