Naive One-Pass C++ Solution of O(n) Time and Space --- Any suggestions?


  • -1

    The following idea is pretty naive.

    Since we need to make a deep copy of the list and nodes in the list have a random pointer that may point to any node in the list (or NULL), we maintain a mapping from each node in the origianl list to the node in the copy list. If the copy of a node already exists, just use that copy without copying it again; otherwise, create a new copy and add it to the mapping.

    The following code is pretty straight-forward.

    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            if (!head) return NULL;
            mp[head] = new RandomListNode(head -> label);
            RandomListNode* run = head;
            RandomListNode* temp = mp[head];
            while (run) {
                /* Process the next pointer */
                if (run -> next) {
                    if (mp.find(run -> next) == mp.end())
                        mp[run -> next] = new RandomListNode(run -> next -> label);
                    temp -> next = mp[run -> next];
                }
                /* Process the random pointer */
                if (run -> random) { 
                    if (mp.find(run -> random) == mp.end())
                        mp[run -> random] =  new RandomListNode(run -> random -> label);
                    temp -> random = mp[run -> random];
                }
                run = run -> next;
                temp = temp -> next;
            }
            return mp[head];
        }
    private:
        unordered_map<RandomListNode*, RandomListNode*> mp;
    };
    

    Any suggestions :-)


Log in to reply
 

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