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

O(2n） 遍历两遍就行

struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* ph) {
        if(!ph) return ph;    
        unordered_map<RandomListNode*, RandomListNode*> mp;    
        RandomListNode *ans=new RandomListNode(0);   
        RandomListNode *p1=ans,*temp=ph;   
        while(temp){
            RandomListNode* t = new RandomListNode(temp->label); 
            p1->next = t;    
            mp[temp] = t;  
            temp = temp->next;   
            p1 = p1->next;
        }
        temp=ph;
        p1=ans->next;
        while(temp){
            p1->random=mp[temp->random];
            temp=temp->next;
            p1=p1->next;
        }
        return ans->next;
    }
};