[C++] sharing my stripped off version of "clone graph"

• I'm sharing my C++ solution. Like other people on discuss, "clone graph" immediately came to my mind. Forget about the code my now. If you solved the "clone graph" problem, the `for` loop over neighbors reduces to two hard coded cases. One for the `next` neighbor and the other for the `random` neighbor. If you haven't solved the "clone graph" problem, I suggest you complete that problem first because this problem trivially reduces to a simpler but identical problem. If I'm needlessly forcing a generic solution here to reuse the code, etc and there exists a much better algorithm to solve this problem, I'm open to suggestions.

``````class Solution {
public:
RandomListNode* helper(RandomListNode* curnode, unordered_map<RandomListNode*, RandomListNode*> &dict){
// whenever I "new" a node, create an entry in the hash table.
RandomListNode* curnode_copy = new RandomListNode(curnode->label);
dict[curnode] = curnode_copy;

// Update the link for the nextnode
RandomListNode* nextnode = curnode->next;
if (nextnode){
if (dict.find(nextnode)==dict.end()) // if haven't seen before
dict[curnode]->next = helper(nextnode, dict);
else
dict[curnode]->next = dict[nextnode];
}

// Update the link for the randomnode
RandomListNode* randomnode = curnode->random;
if (randomnode){
if (dict.find(randomnode)==dict.end())
dict[curnode]->random = helper(randomnode, dict);
else
dict[curnode]->random = dict[randomnode];
}
return curnode_copy;
}

unordered_map<RandomListNode*, RandomListNode*> dict;
}
};``````

• My solution is the same as yours，but mine is iterative. So it's faster than yours in theory,haha.

``````RandomListNode *copyRandomList(RandomListNode *head) {

unordered_map<RandomListNode *, RandomListNode *> umap;
unordered_map<RandomListNode *, RandomListNode *>::iterator it;

rlp->random = NULL;
if (it == umap.end()) {
} else {
rlp->random = it->second;
}
}

if (it == umap.end()) {
} else {
rlp->next = it->second;
}
rlp = rlp->next;
}

rlp->next = NULL;
• The hash table is used to update the link for the copy of the current node. Please look at the comment in the code. Basically, `dict[curnode]->next` and `dict[curnode]->random` provides the necessary mechanism to do that.