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

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
//1.用vector的下标表示连续的每个结点的位置，值表示random的下标。值通过如下方式寻找：
//每次count=0，每次q从头开始遍历，遍历到和当前结点的random是同一个结点时break，count就是值
//2.复原：首先遍历一遍原始链表，创建实线的单列表；然后根据vector中记录的相对关系逐个指定random。
//时间复杂：n^2 ； 空间复杂：n

#include <vector>
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        vector<int> randomPos;
        if(pHead==nullptr)  return nullptr;
        //保存随机结点的位置信息
        RandomListNode * p = pHead;
        while(p){
            RandomListNode * temp = p->random;
            RandomListNode * q = pHead;
            int count=0;
            while(true){
                if(temp==nullptr){
                    count = -1;
                    break;
                }
                if(q==temp) break;
                count++;
                q = q->next;
            }
            randomPos.emplace_back(count);
            p = p->next;
        }

        //新建实线链表
        auto * res_head = new RandomListNode(pHead->label);
        RandomListNode * res_q = res_head;
        p = pHead;
        while(p){
            if(p->next!=nullptr){
                auto * temp = new  RandomListNode(p->next->label);
                temp->next = nullptr;
                temp->random = nullptr;
                res_q->next = temp;
                res_q = temp;
            }
            p = p->next;
        }

        //根据vector建立random关系
        p = res_head;
        for(int i =0;i<randomPos.size();i++){
            int pos = randomPos[i];
            if(pos==-1) {
                p = p->next;
                continue;
            }
            res_q = res_head;//找到当前结点的random
            for(int j=0;j<pos;j++){
                res_q = res_q->next;
            }
            p->random = res_q;
            p = p->next;
        }

        return res_head;

    }
};