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

//第一次遍历复制链表并保存旧链表与新链表映射关系，第二次遍历赋值新链表的随机指针

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;					
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        map<RandomListNode*, RandomListNode*> oldToNewMaps; //用来保持新旧指针映射
        
        //遍历一遍，新建单链表，并建立旧链表与新链表节点映射
        RandomListNode *node = pHead, *newHead = nullptr, *newNode;
        while (node) {
            if (newHead == nullptr) {
                newNode = newHead = new RandomListNode(node->label);
            } else {
                newNode->next = new RandomListNode(node->label);
                newNode = newNode->next;
            }
            
            oldToNewMaps[node] = newNode;
            node = node->next;
        }
        
        //遍历一遍，根据映射，赋予随机指针
        node = pHead;
        newNode = newHead;
        while (node) {
            newNode->random = oldToNewMaps[node->random];
            node = node->next;
            newNode = newNode->next;
        }
        
        return newHead;
    }
};