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


  • 0
    S

    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;    
        }
    
        RandomListNode *copyRandomList(RandomListNode *head) {
            if (!head) return NULL;
            unordered_map<RandomListNode*, RandomListNode*> dict;
            return helper(head, dict);
        }
    };

  • 0
    O

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

    RandomListNode *copyRandomList(RandomListNode *head) {
        if (!head) return NULL;
    
        unordered_map<RandomListNode *, RandomListNode *> umap;
        unordered_map<RandomListNode *, RandomListNode *>::iterator it;
        RandomListNode *copyHead = new RandomListNode(head->label);
        RandomListNode *rlp = copyHead;
    
        umap[head] = copyHead;
    
        while (head->next) {
            rlp->random = NULL;
            if (head->random) {
                it = umap.find(head->random);
                if (it == umap.end()) {
                    rlp->random = new RandomListNode(head->random->label);
                    umap[head->random] = rlp->random;
                } else {
                    rlp->random = it->second;
                }
            }
    
            it = umap.find(head->next);
            if (it == umap.end()) {
                rlp->next = new RandomListNode(head->next->label);
                umap[head->next] = rlp->next;
            } else {
                rlp->next = it->second;
            }
            rlp = rlp->next;
            head = head->next;
        }
    
        rlp->next = NULL;
        rlp->random = head->random ? umap[head->random] : NULL;
        return copyHead;
    }

  • 0
    R

    why need unorded_map


  • 0
    S

    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.


  • 0
    S

    I've accepted this solution but haven't checked if this is actually faster than my recursive solution (my solution passes the OJ).


Log in to reply
 

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