Clear C++ solution with O(n) time and O(n) memory


  • 0
    A

    My idea was to only create first a copy of the nodes from head by setting only the next field to the newly copied nodes, and this for each node from the initial list.
    During this process, an unordered_map is also used in order to keep track of the random field for all nodes from the initial list.
    Then, this unordered_map will be used in a second walk through the initial list, to set the random field properly.

    class Solution {
    private:
    
        typedef RandomListNode* r_list_t;
        typedef std::unordered_map<RandomListNode*, r_list_t> map_t;
    
        r_list_t copyListWithoutRandom(r_list_t head, map_t& nodeMap) {
    
            if (head == NULL) {
                return NULL;
            }
    
            RandomListNode* newNode = new RandomListNode(head->label);
            RandomListNode* prevNode = copyListWithoutRandom(head->next, nodeMap);
    
            newNode->next = prevNode;
            nodeMap[head] = newNode;
    
            return newNode;
        }
    
    public:
    
        RandomListNode *copyRandomList(RandomListNode *head) {
    
            map_t nodeMap;
            r_list_t headTmp = head;
            /* create a copy of head, without the random field
               and store in a map with references to all nodes created */
            r_list_t copyList = copyListWithoutRandom(headTmp, nodeMap);
    
            /* copy also the random field */
            headTmp = head;
            r_list_t copyListTmp = copyList;
            while (headTmp != NULL) {
    
                if (headTmp->random != NULL) {
                    copyListTmp->random = nodeMap[headTmp->random];
                }
    
                headTmp = headTmp->next;
                copyListTmp = copyListTmp->next;
            }
    
            return copyList;
        }
    };
    

Log in to reply
 

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