C++ 6 lines recursive solution using memoization


  • 14
    B
    class Solution {
    public:
        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
    W

    don`t understand but look like awesome


  • 0
    C

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


  • 0
    B

    @Carrot21

    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
    E

    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.