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

//这题我有两个思路吧。如果Label能保证是不重复的话，嗯遍历就行了，只要靠Label就能找到Random指向的节点是谁。这题也确实是这样的。
//但如果不能通过Label来确定的话，就需要维护一个映射了，在构建基础链表的过程就要建立起从源链表到新链表的映射，然后回过头来遍历源链表时，就知道源链表里指的Random对应到新链表里是哪个节点了。如果不这么干的话，时间复杂度会高很多。
/*
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==nullptr)
            return nullptr;
        RandomListNode* result=new RandomListNode(pHead->label);
        RandomListNode* OriginCurrent=pHead;
        RandomListNode* NewCurrent=result;
        while (OriginCurrent->next) {//先创建一遍基础的模样
            OriginCurrent=OriginCurrent->next;
            RandomListNode* NewNode=new RandomListNode(OriginCurrent->label);
            NewCurrent->next=NewNode;
            NewCurrent=NewNode;
        }
        OriginCurrent=pHead;
        NewCurrent=result;
        while(OriginCurrent)
        {
            RandomListNode* RandomTarget=result;
            if(OriginCurrent->random)
            {
                int randomLabel=OriginCurrent->random->label;
                while(RandomTarget)//在新链表中确定random的指向
                {
                    if(RandomTarget->label==randomLabel)
                    {
                        NewCurrent->random=RandomTarget;
                    }
                    RandomTarget=RandomTarget->next;//遍历新链表找到randomTarget
                }
            } 
            OriginCurrent=OriginCurrent->next; 
            NewCurrent=NewCurrent->next;       
        }
        return result;
    }
};