题解 | 复杂链表的复制 相对位置相同求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) {
        //如何找到random 相对位置
        //先复制全部
        if(!pHead)
        {
            return nullptr;
        }
        RandomListNode* cur=pHead;
        RandomListNode* new_phead=new RandomListNode(pHead->label);
        RandomListNode* new_cur=new_phead;
        cur=cur->next;
        while(cur)
        {
            new_cur->next=new RandomListNode(cur->label);
            new_cur=new_cur->next;
            cur=cur->next;
        }
        new_cur->next=nullptr;
        //复制random节点相对位置
        cur=pHead;
        new_cur=new_phead;
        RandomListNode* cur2=cur;
        while(cur)
        {
            int i=0;
            cur2=pHead;
            while(cur2!=cur->random)
            {
                i++;
                cur2=cur2->next;
            }
            RandomListNode* new_cur2=new_phead;
            while(i)
            {
                new_cur2=new_cur2->next;
                i--;
            }
            new_cur->random=new_cur2;
            new_cur=new_cur->next;
            cur=cur->next;

        }
        return new_phead;
    }
};