C++ simple recursive solution


  • 20
    J
    class Solution {
    unordered_map<RandomListNode*, RandomListNode*> hmap;
    
    public:
    RandomListNode *copyRandomList(RandomListNode *head) {
    	if (!head) return NULL;
    	if (hmap.find(head) != hmap.end())
    		return hmap.find(head)->second;
    
    	RandomListNode* node = new RandomListNode(head->label);
    	hmap[head] = node;
    	node->next = copyRandomList(head->next);
    	node->random = copyRandomList(head->random);
    	return node;
    }
    };

  • 0

    Excellent Solution! But if I write hmap[head] = node; after node->random = copyRandomList(head->random);, just as the follow, it will get a Runtime Error.

    I am confused, can you tell me the difference between the two codes?

    class Solution {
    private:
        unordered_map<RandomListNode*, RandomListNode*> hmap;
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            if (!head) return NULL;
            if (hmap.find(head) != hmap.end())
                return hmap.find(head)->second;
            RandomListNode* node = new RandomListNode(head->label);
            node->next = copyRandomList(head->next);
            node->random = copyRandomList(head->random);
            hmap[head] = node;
            return node;
        }
    };
    

    Closed: I get the reason, thank you!


  • 0

    Very great solution: simple, concise and easy to understand :-) BTW, hmap.find(head)->second can simply be hmap[head].


  • 0
    V

    Concise and beautiful !


  • 0

    @prime_tang
    The difference is that, Rand pointer might point to itself. By first writing a node into the hash table, the recursion prevents infinite loop of pointer->rand(self)->rand(self)->...


Log in to reply
 

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