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

/*
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) return NULL;
      
        RandomListNode *cur = pHead;
        while(cur){
            RandomListNode *temp = new RandomListNode(cur->label);
            temp->next = cur->next;
            cur->next = temp;
            cur = temp->next;
        }
        cur = pHead;
        while(cur){
            if(cur->random)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        RandomListNode *head = new RandomListNode(0);
        head->next = pHead;
        cur = head;
        while(cur->next){
            RandomListNode* p = cur->next;
            cur->next = cur->next->next;
            free(p);
            cur = cur->next;
        }
        return head->next;
    }
};