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

我知道还有其他类似的问题，但它们对我没有帮助。我还尝试过使用递归以外的其他方法，例如while循环，看起来像：

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循环外复制的第一个节点）。

非常感谢您的帮助。谢谢

Answer 1

如果您是初学者，请从简单的事情开始：在理解循环之前尽量避免递归。所以我只评论循环版本（无论如何，递归是解决这个特定问题的糟糕方法）。

如果代码没有达到你想要的效果，你应该试着在调试器中遍历它，记下它到底做了什么，或者试着把它解释为一系列指令给别人（橡皮鸭非常适合这样做，因为它很有耐心）。

你也可以通过对代码进行推理来解决这个问题：

每个变量都应该有一个明确定义的目的，最好体现在其名称中。我可以看到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;
}