我正在尝试深度复制链表。我需要一个在线性时间 O(n) 内执行的算法。这就是我现在所拥有的,但我无法弄清楚它出了什么问题。我的应用程序崩溃了,我怀疑内存泄漏,我还没有弄清楚。这就是我现在拥有的
struct node {
struct node *next;
struct node *ref;
};
struct node *copy(struct node *root) {
struct node *i, *j, *new_root = NULL;
for (i = root, j = NULL; i; j = i, i = i->next) {
struct node *new_node;
if (!new_node)
{
abort();
}
if (j)
{
j->next = new_node;
}
else
{
new_root = new_node;
}
new_node->ref = i->ref;
i->ref = new_node;
}
if (j)
{
j->next = NULL;
}
for (i = root, j = new_root; i; i = i->next, j = j->next)
j->ref =i->next->ref;
return new_root;
}
谁能指出我哪里出错了??
最佳答案
仅此部分:
struct node *new_node;
if (!new_node)
{
abort();
}
似乎适合随机 abort()
发生。 new_node
未分配并将包含一个随机值。 !new_node
表达式可能已经是致命的(在某些系统上)。
作为一般提示,您应该只需要 1 个 for 循环。一些预先建立 new_root
的代码。
但真正的深拷贝还需要克隆 ref
指向的任何内容。在我看来,第二个循环将原件中的某些内容分配给了拷贝。但我不确定,ref
是什么?
关于c++ - 深度复制链表 - O(n),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5057755/