C++ solution


  • 0
    T

    Go through the link list twice.
    The first time, only copy the link list without considering the random pointer(just leave it NULL). Use a map to store the mapping between the node coming from original list to the node coming from copied list.
    The second time, we can setup the random pointer one by one from the map that we had in first round go through.

    class Solution {
    public:

    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head==NULL)
            return NULL;
        RandomListNode *newRoot=new RandomListNode(head->label);
        RandomListNode *oldRoot=head;
        unordered_map<RandomListNode *, RandomListNode *>m;
        m[head]=newRoot;
        RandomListNode *newHead=newRoot;
    
        while(head->next!=NULL){
            head=head->next;
            RandomListNode *newNode=new RandomListNode(head->label);
            newHead->next=newNode;
            newHead=newNode;
            m[head]=newHead;
        }
        head=oldRoot;
        newHead=newRoot;
        while(head!=NULL){
            newHead->random=m[head->random];
            newHead=newHead->next;
            head=head->next;
        }
        return newRoot;
    }
    

    };


Log in to reply
 

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