天天看點

複雜連結清單的複制

. 複雜連結清單的複制

題目介紹:

Node(int _val) {
    val = _val;
    next = NULL;
    random = NULL;
}           
### 題解
1. 這道題是一道 基于深拷貝 思想的連結清單題,意味着一定要做到深拷貝,将整個資源copy一份
2. 特殊的,處理尋常連結清單具有的 next的指針, 它還有 一個指向 随機的 random的指針
3. 對于深度拷貝,必然我們要主動  建立每一個節點,才能實作整體的拷貝
4. 因為具有一個随機的指向, 是以, 為了不 多次的建立某一節點, 我們選擇使用一個 單次存儲的map來管理建立的資源
5. -------------------------分割線------------------------------------------------------------
6. 利用一個map 對需要建立head的拷貝值node時, 進行插入實作管理
7. 如果已經建立過了,就不需要再做處理, 沒有建立的話, 進入
8. 建立改節點的拷貝,插入, 然後深度拷貝 它的next 節點和 random節點
9. 因為利用的遞歸,偏向于深度的一種建構,對于連結清單來說,就可以說是完成了
10. 傳回值是copy的新的頭節點, 即map --> key == head;           

繼續閱讀