【C++項目實戰】随機連結清單建立和深拷貝（克隆）

知識點

題目來源：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

• 結構體使用
• 連結清單建立
• 遞歸算法
• 引用傳參
• 哈希表使用

代碼

#include<iostream>
#include<unordered_map>
using namespace std;
struct Node{ // 建立結構體
    int val; // 節點值
    Node *next, *random; // 節點指針
    Node(int x): val(x), next(nullptr), random(nullptr){}; // 節點初始化
};

unordered_map<Node*, Node*> dic; // 建立鍵值都為Node類型位址的哈希表

Node* copyRandomList(Node* head) { // 克隆指針函數
    if (head == nullptr) return nullptr;  // 遞歸傳回條件1，節點不存在則傳回nullptr
    if (dic.count(head)) return dic[head]; // 遞歸傳回條件2，節點已在哈希表中，則傳回對應值
    Node* root = new Node(head->val); // 節點不在哈希表，說明克隆節點還未建立，則建立之
    dic[head] = root; // 建立原節點和克隆節點對應關系
    // cout << "R0-" << head->val << ' ';
    root->next = copyRandomList(head->next); // 第一次遞歸，連接配接連結清單
    // cout << "R1-"  << head->val << ' ';
    root->random = copyRandomList(head->random);// 第二次遞歸，将随機指針連接配接上
    return root; // 傳回節點
    // 程式運作過程，第一次遞歸會完成所有克隆節點建立并放入哈希表，第二次遞歸連接配接上即可
    // 取消兩個cout的注釋，得到的輸出是：
    // R1-0 R1-1 R1-2 R1-3 R1-4 R2-4 R2-3 R2-2 R2-1 R2-0
    // 前面5個是節點建立順序，後面5個是random指針的連接配接順序（此時節點已全部建立完畢）
}

int main(){
    int arr[] = {3,1,4,0,2};
    Node head(0);
    unordered_map<int,Node*>mp; /
    Node *p1 = &head; 
    mp[0] = &head;
    for (int i=1; i<5; ++i){
        p1->next = new Node(i);    
        p1 = p1->next;    
        mp[i] = p1;
    }
    p1 = &head; 
    for (int i=0; i<5; ++i){
        p1->random = mp[arr[i]];
        p1 = p1->next;
    }
    Node *clone = copyRandomList(&head);
    return 0;
}
           

後記

• 結構體的關鍵字是struct，其文法結構與class基本相同，主要差別在于結構體預設成員變量和函數都是public，而class預設的成員變量和函數是private（類外不可調用）
• 哈希表的鍵值可以是指針指向的位址，例如

  unordered_map<int*, int*> dic

• 遞歸算法可以代替使用循環，提高程式的可讀性，但并不提高效率