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

# 第七题
/*
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==NULL)
            return NULL;
        // 题目都看不懂TAT
        
        // 好像意思是 给他这个一模一样复制出来
        // 12345啥的next就是正常的指针链接到最后
        // 35#2# 是前面12345里面的random的指针
        // random的指针指向指定的值 3 就代表random指向第三个，#代表random指向空

        // 用来返回的答案
        RandomListNode* ans=new RandomListNode(0);
        // ans会动 ret_ans保存ans的头
        RandomListNode* ret_ans=new RandomListNode(0);
        ret_ans->next=ans;
        // 保存
        RandomListNode* head=pHead;
        
        // 后面一直要用到，防止创建的时候复杂度大 先声明了到时候直接用
        RandomListNode* temp=ans;
        
        // 先遍历一遍，把12345整个链表的next保存下来
        while(pHead!=NULL){
            // 调试的时候输出的 看他这里面到底是个啥
            // cout<<pHead->label<<" "<<pHead->random<<endl;
            ans->label=pHead->label;
            pHead=pHead->next;
            
            // 如果pHead 后面没了 就不创建新节点了
            if(pHead!=NULL){
                // 新建的链表每个结点12345每次都是要new出来
                // 不然直接 ans=ans->next 会访问空指针报错
                ans->next=new RandomListNode(NULL);
                ans=ans->next;
            }
        }

        // 让ans、pHead回到开头
        ans=ret_ans->next;
        pHead=head;
        // 决定了每次要走几步 就是random的值是几 比如说 是3，就说明后面要重新走到三的位置
        int go_temp;
        // 从现在开始 处理pHead里面random的内容
        while(pHead!=NULL)
        {
            // 如果是# random直接指向空 然后 各自往后走一个
            if(pHead->random == NULL)
            {
                ans->random=NULL;
                ans=ans->next;
                pHead=pHead->next;
                continue;
            }
            
            // temp是用来重头找random的点的
            // 比如说go_temp是3，就代表往后指向第三个，从temp开始走的
            temp=ret_ans->next;
            go_temp = pHead->random->label;

            // go_temp是1，就代表指向第一个，链表不用向后走
            // go_temp是2，就代表指向第二个，链表向后走一次就可
            while(go_temp !=1 ){
                temp=temp->next;
                go_temp--;
            }
            // ans 指向了random需要的
            ans->random=temp;
            
            // ans 和pHead各自往后走一个向后循环做下去。。。。。
            ans=ans->next;
            pHead=pHead->next;
        }
        return ret_ans->next;
    }
};