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

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        // 先复制新值
        for( auto p = pHead; p;)
        {
            auto newp = new RandomListNode(p->label);
            auto temp = p->next;
            p->next = newp;
            newp->next = temp;
            p = temp; 
        }
        // 复制random值
        for( auto p = pHead; p ; p = p->next->next )
        {
            if(p->random)
                p->next->random = p->random->next;
        }
        // 最后把它裁剪出来
        auto dummy = new RandomListNode(-1);
        auto cur = dummy;
        for( auto p =pHead; p ; p = p->next)
        {
            cur->next = p->next;
            cur = cur->next;
            p->next = p->next->next;
        }
        return dummy->next;
    }
};