O(n) C++ solution using hash


  • 0
    L

    First I go through the list and make new one with same data. At the same time I'm mapping previous and new pointers to node. After that I just run through the list again and just assign the random pointers from hash to the new list.

    RandomListNode *copyRandomList(RandomListNode *head) {
        if (head == NULL) return NULL;
        RandomListNode * hh = new RandomListNode(head->label);
        RandomListNode * ret = hh;
        RandomListNode * cur = head;
        unordered_map<RandomListNode*, RandomListNode*> pmap;
        pmap[head] = hh;
        while(cur->next) {
            cur = cur->next;
            hh->next = new RandomListNode(cur->label);
            hh = hh->next;
            pmap[cur] = hh;
        }
        cur = head;
        while(cur) {
            if(pmap.count(cur)) {
                hh = pmap[cur];
                if (cur->random && pmap.count(cur->random)) {
                    hh->random = pmap[cur->random];
                }
            }
            cur = cur->next;
        }
    
        return ret;
    }

Log in to reply
 

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