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

/*
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) {
        if (!pHead) return nullptr;
        
        std::map<RandomListNode *, RandomListNode *> old2new;
        auto p = pHead;
        while (p) {
            auto node = new RandomListNode(p->label);
            old2new.emplace(p, node);
            p = p->next;
        }

        for (const auto &[old_node, new_node] : old2new) {
            new_node->next = old2new[old_node->next];
            new_node->random = old2new[old_node->random];
        }

        return old2new[pHead];
    }
};