複雜的連結清單的深度拷貝

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];
    }
};           

複制