C++ 6 lines recursive solution using memoization

  • 14
    class Solution {
        unordered_map<RandomListNode*, RandomListNode*>mp;
        RandomListNode *copyRandomList(RandomListNode *head) 
            if(!head) return NULL;
            if(mp[head]!=NULL) return mp[head];
            mp[head] = new RandomListNode(head->label);
            mp[head] -> next = copyRandomList(head->next);
            mp[head] -> random = copyRandomList(head->random);
            return mp[head];

  • 0

    don`t understand but look like awesome

  • 0

    I'd appreciate it if you can explain your code for me, because your code is the most
    beautiful that I have seen !

  • 0


    I think it is pretty straight forward. what is your question?

    function copyRandomList should return a copy of input node, and the next and random pointer can also get their copies by calling the same function. The HashMap is used to store previous results.

  • 0

    Here are my thoughts.

    The key of map is the original list's node, the value of map is the new list node.
    And mp[head]!=NULL means current node has been reached and copied, return mp[head] returns the referring of it.

    Beautiful code. Thanks a lot.

Log in to reply

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