Sharing my O(N) C++ solution using unordered_map


  • 2
    T
    /**
     * Definition for singly-linked list with a random pointer.
     * struct RandomListNode {
     *     int label;
     *     RandomListNode *next, *random;
     *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
     * };
     */
     
    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            // use unordered_map to do O(N) deep copy
            if(head==NULL)
                return NULL;
            RandomListNode* newHead = new RandomListNode(head->label);
            RandomListNode* oldp = head;
            RandomListNode* newp = newHead;
            unordered_map<RandomListNode*, RandomListNode*> myMap;
            myMap[oldp] = newp;
            while(oldp->next)
            {
                RandomListNode* temp = new RandomListNode(oldp->next->label);
                newp->next = temp;
                myMap[oldp->next] = newp->next;
                oldp = oldp->next;
                newp = newp->next;
            }
            
            oldp = head;
            newp = newHead;
            while(oldp)
            {
                if(oldp->random == NULL)
                    newp->random = NULL;
                else
                    newp->random = myMap[oldp->random];
                    
                oldp = oldp->next;
                newp = newp->next;
            }
            
            return newHead;
        }
    };

Log in to reply
 

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