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

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

        RandomListNode * pCur = pHead;
        unordered_map<RandomListNode *,RandomListNode *> map_tmp;
        //map里存放原节点->新节点的映射关系
        while (pCur != NULL) 
        {
            RandomListNode * pNode = new RandomListNode(pCur->label);
            map_tmp[pCur] = pNode;
            pCur = pCur->next;
        }

        //根据原节点里的指针指向映射出新节点的指针指向
        pCur = pHead;
        while (pCur != NULL) 
        {
            map_tmp[pCur]->next = map_tmp[pCur->next];
            map_tmp[pCur]->random = map_tmp[pCur->random];
            pCur = pCur->next;
        }

        return map_tmp[pHead];
    }
};