剑指 Offer 35. 复杂链表的复制

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(pHead == NULL)
            return NULL;
        //建立map,存储旧节点到新节点的映射
        map<RandomListNode*,RandomListNode*> mymap;
        RandomListNode* cur = pHead;
        while(cur){
            RandomListNode* node = new RandomListNode(cur->label);
            mymap[cur] = node;
            cur = cur->next;
        }
        //考虑next,random指针为NULL的情况
        mymap[NULL] = NULL;
        cur = pHead;
        //在遍历一次,存储next,random指针
        while(cur){
            mymap[cur]->next = mymap[cur->next];
            mymap[cur]->random = mymap[cur->random];
            cur = cur->next;
        }
        return mymap[pHead];
    }
};