C++深度複製鏈接列表

Question

我是一名C++初學者，嘗試編寫一個函數來創建C++中鏈接列表的深層副本。該函數調用自身，直到它位於源列表中的最後一個節點，然後複製該節點。但是，當我運行這個我得到一個分段錯誤或EXC_BAD_ACCESS錯誤。這是我到目前爲止：

struct node { 
int data; 
node* next; 
};  


void copy_list(const node*& source_ptr, node*& dest_ptr) 
{ 
if (dest_ptr != nullptr){ 
    clear_list(dest_ptr); 
    } 

if (source_ptr == nullptr) return; //we already cleared dest_ptr 

if (source_ptr->next == nullptr) // this is the last node 
{ 
    dest_ptr = new node(); //initialize in memory 
    dest_ptr->data = source_ptr->data; //copy the last datum 
    dest_ptr->next = nullptr; //since this is the end 
    return; 
} 
const node* cursor = source_ptr->next; // this happens if source is not yet at the end 

copy_list(cursor, dest_ptr->next); 
} 

我知道還有其他類似的問題，但他們沒有幫助我。

dest_ptr = new node(); 
dest_ptr->data = source_ptr->data; 
node* dest = dest_ptr->next; 
const node* cursor = source_ptr->next; 

while(cursor != nullptr) 
{ 
    dest = new() node; 
    dest-> data = cursor->data; 
    //dest->next = nullptr; 
    dest = dest->next; 
    cursor = cursor->next; 
} 

while循環不給錯誤，但複製是空白的（除了被外界所複製的第一個節點：我已經使用其他方法比遞歸例如while循環，看起來像也嘗試while循環）。

任何幫助，非常感謝。謝謝！

Answer 1

如果您是初學者，請從簡單的事情開始：在理解循環之前儘量避免遞歸。所以我只會對循環版本發表評論（無論如何，遞歸對這個特定問題都是一個壞的方法）。

如果代碼沒有做到你想要的，你應該嘗試在調試器中單步執行它，以確定它究竟做了什麼，或者試圖將它解釋爲對某人的指令列表（rubber duck是理想的，因爲它是耐心的）。

您還可以通過推理代碼接近這個：

每個變量都應該有一個明確的目的，最好體現在它的名字。我可以看到source_ptr的目的是指向源列表。而cursor的用途是遍歷源列表。

dest_ptr可能是爲了保存新創建的副本。通過將第一個data複製到其中，您的開局很好。但是，dest的目的是什麼？您首先將dest_ptr->next（實際上將爲null）的值複製到其中。然後，在循環中，您立即用新創建的節點覆蓋dest。將cursor->data複製到此新節點中，並將此（未初始化）指針dest->next複製到dest。但是請注意，您從不讀取dest的值，您只需在下一次迭代中覆蓋它。

我懷疑你真正意圖dest是一個指針的指針node，你的目的是要做到這一點：

dest_ptr = new node(); 
dest_ptr->data = source_ptr->data; 
node **dest = &dest_ptr->next; 
const node *cursor = source->ptr->next; 

while (cursor) 
{ 
    *dest = new node(); 
    (*dest)->data = cursor->data; 
    dest = &((*dest)->next); 
    cursor = cursor->next; 
} 

這將做你想要的，但指針的指針是醜陋的。這將是更好地使用dest作爲第二光標用於遍歷目的地列表：

dest_ptr = new node(); 
dest_ptr->data = source_ptr->data; 
node *dest = dest_ptr; 
const node *cursor = source_ptr->next; 

while (cursor) 
{ 
    dest->next = new node(); 
    dest = dest->next; 
    dest->data = cursor->data; 
    cursor = cursor->next; 
}