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

/*
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 pHead;
        }
        unordered_map<RandomListNode*, RandomListNode*> maps;

        RandomListNode* dummy = new RandomListNode(-1);
        RandomListNode* pre = dummy;
        RandomListNode* cur = pHead;

        while(cur) {
            RandomListNode *tmp = new RandomListNode(cur->label);
            pre->next = tmp;
            // 这里不能加 if(cur)
            maps[cur] = tmp; // 记录映射

            pre = pre->next;
            cur = cur->next;
        }

        for (auto & [key, clone]: maps) {
            clone->random = key->random == nullptr? nullptr: maps[key->random];
        }
        return dummy->next;
    }
};

这道题的思路我是理解的，但是提交的时候一直错

后面参考了答案后才反应过来， 是自己中间加了判断条件：

判断 如果当前 node->random 存在，就把他放入hash map中， 这样做看似是合理的

但实际上在下面build random的时候，你会发现map[key->random]有一些不存在了就是这个原因