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

/*
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;
        RandomListNode* cur=pHead;
        unordered_map<RandomListNode*, RandomListNode*> map;
        while (cur) {
            map[cur] = new RandomListNode(cur->label);
            cur = cur->next;
        }
        cur = pHead;
        while (cur) {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        return map[pHead];

    }
};

使用键值对哈希表unordered_map，首先遍历原链表，建立原链表节点和拷贝链表节点之间的映射关系，然后再建立拷贝节点之间的连接关系，包括Next和random