A solution with O(n) time complexity and cost 52 ms.


  • 0
    A

    The idea is simple. Marking each node a unique integer, and use two hash map, one uses the point as key, and the marked integer as value, another one uses the marked integer as key and corresponding point as value.

     RandomListNode *copyRandomList(RandomListNode *head)
     {
            RandomListNode* point=new RandomListNode(0);
            RandomListNode* head_point=point;
            RandomListNode* head_copy=head;
            unordered_map<RandomListNode*,int> point_position;
            unordered_map<int,RandomListNode*> position_point;
            int count=1;
            while(head!=NULL)
            {
                point->next=new RandomListNode(head->label);
                point_position[head]=count;
                position_point[count]=point->next;
                point=point->next;
                head=head->next;
                count++;
            }
            head=head_copy;
            point=head_point->next;
            while(head!=NULL)
            {
                point->random=position_point[point_position[head->random]];
                head=head->next;
                point=point->next;
            }
    
        return head_point->next;
    }
    

    '''


Log in to reply
 

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