Straight forward and concise O(2n) solution


  • 0
    S

    // here it needs two pass for the concise, you can improve it to one pass which doing creating new nodes and set random pointers

    RandomListNode *copyRandomList(RandomListNode *head) {
                if (!head) return NULL;
                
                unordered_map<RandomListNode *, RandomListNode *> hm;
                RandomListNode *p = head, *rHead = NULL, *rp = NULL;
                
                // deep copy header
                rHead = new RandomListNode(p->label);
                rp = rHead;
                hm[p] = rp;
                
                // deep copy the other nodes
                p = p->next;
                while(p) {
                    rp->next = new RandomListNode(p->label);
                    rp = rp->next;
                    hm[p] = rp;
                    p = p->next;
                }
                
                // deep copy random pointer
                p = head, rp = rHead;
                while(p) {
                    if (p->random) {
                        rp->random = hm[p->random];
                    }
                    p = p->next;
                    rp = rp->next;
                }
                
                return rHead;
            }

Log in to reply
 

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