c++ - 深度复制链表 - O(n)

Question

我正在尝试深度复制链表。我需要一个在线性时间 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;
}

谁能指出我哪里出错了？？

Answer 1

仅此部分:

    struct node *new_node;
    if (!new_node) 
    {
        abort();
    }

似乎适合随机 abort() 发生。 new_node 未分配并将包含一个随机值。 !new_node 表达式可能已经是致命的(在某些系统上)。

作为一般提示，您应该只需要 1 个 for 循环。一些预先建立 new_root 的代码。

但真正的深拷贝还需要克隆 ref 指向的任何内容。在我看来，第二个循环将原件中的某些内容分配给了拷贝。但我不确定，ref 是什么？