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

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        int x=0;
        RandomListNode *pre = new RandomListNode(0);
        RandomListNode *last = pre;
        RandomListNode *p = pHead;
	  //这里使用map把random的值存下来，再次遍历时进行赋值
        unordered_map<int, RandomListNode*> map;
        while(p)
        {
            RandomListNode *node = new RandomListNode(p->label);
            map[node->label] = node;
            last->next = node;
            last = last->next;
            p = p->next;
        }
        p = pHead;
        last = pre->next;
        while(p)
        {
            if(p->random)
            {
                last->random = map[p->random->label];
            }
            p = p->next;
            last = last->next;
        }
        return pre->next;
    }
};