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