复杂的链表的深度拷贝

Copy List with Random Pointer
已知一个复杂的链表，节点中有一个指向本链表任意某个节点的碎甲指针（也可以为空），求这个链表的深度拷贝。

class Solution{
public:
    RandomListNode *copyRandomList(RandomListNode *head){
    }//返回时深度拷贝后的链表
};//深度拷贝：构造生成一个完全新的链表，即使将原链表毁坏，新链表可独立使用

必备知识，STL Map使用

#include <stdio.h>
#include<map>//STL map头文件
struct RandomListNode{//带有随机指针的链表节点
    int label;
    RandomListNode *next,*random;
    RandomListNode(int x): label(x),next(NULL),random(NULL){}
};
int main(){
    std :: map<RandomListNode *,int> node_map;
    RandomListNode a(5);
    RandomListNode b(3);
    RandomListNode c(6);
    a.next = &b;
    b.next = &c;
    a.random = &c;
    b.random = &a;
    c.ramdom = &c;
   //可以知道j节点位置，在什么位置
    node_map[&a] = 1;//a节点的地址映射为1
    node_map[&b] = 2;
    node_map[&c] = 3;
    printf("a.random id = %d\n",node_map[a.random]);
    printf("b.random id = %d\n",node_map[b.random]);
    printf("c.random id = %d\n",node_map[c.random]);
    return 0;
}

算法：节点地址与节点序号对应，两个映射

主要为了理清逻辑关系

class Solution{
public:
    RandListNode *copyRandomList(RandomListNode *head){
        std::map<RandomListNode*,int> node_map;//map1：地址到节点位置的map
        std::vector<RandomListNode *> node_vec;//map2：使用vector根据存储节点位置访问地址
        RandomListNode *ptr = head;
        int i = 0;
        while(ptr){//将新链表节点push入node_vec,生成了新链表节点位置到地址的map
            node_vec.push_back(new RandomListNode(ptr->label));
            node_map[ptr] = i;//记录原始链表地址至节点位置的node_map
            ptr = ptr->next;//遍历原始列表
            i++;//记录节点位置 
         }
        node_vec.push_back(0)；//特殊处理链表最后一个节点。让链表处理和原来链表是一个统一的状态
        ptr = head;
        i = 0;//再次遍历原始列表，链接新链表的next指针、random指针
        while(ptr){
           node_vec[i]->next = node_vec[i+1];//链接新链表next指针
           if(ptr->random){//当random指针不为空
                   int id = node_map[ptr->random] //根据node_map确认
                   node_vec[i]->random = node_vec[id];原链表random指针指向的位置即id     
                                    } //链接新链表random指针
              ptr = ptr->next;
              i++;
                      }
            return node_vec[0];
    }
};