题解 | #复杂链表的复制#

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
#include <unordered_map>
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        unordered_map<RandomListNode*, RandomListNode*> map;
        if(pHead == nullptr) {
            return nullptr;
        }

        RandomListNode* cur = pHead;
        while(cur) {
            RandomListNode* clone = new RandomListNode(cur->label);
            map[cur] = clone;
            cur = cur->next;
        }

        for(auto it = map.begin(); it != map.end(); ++it) {
            RandomListNode* key = it->first;
            RandomListNode* value = it->second;
            if(key->next!=nullptr)
                value->next = map[key->next];

            value->random = key->random == NULL ? NULL : map[key->random];
        }
        
        // 释放原链表的节点
        // for(auto it = map.begin(); it != map.end(); ++it) {
        //     delete it->first;
        // }
        return map[pHead];
    }
};