深度复制链表 - 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？

Answer 2

我立即注意到的一件事是你从不为 new_node 分配空间。由于不能保证自动变量被初始化，因此 new_node 将被设置为该内存中之前的任何值。您可能应该从以下内容开始：

struct node *new_node = (new_node *) malloc(sizeof(struct node));

在 C 中，或者如果您使用 C++：

node* new_node = new node;

复制列表非常简单。然而，引用指针指向新列表中相对于源列表的相同节点的要求将很难以任何有效的方式实现。首先，您需要某种方法来识别相对于它们指向的源列表的哪个节点。您可以在每个节点中放置某种标识符，例如在第一个节点中设置为 0 的 int，在第二个节点中设置为 1 等。然后在复制列表后，您可以再次遍历列表进行设置参考指针。这种方法（除了向每个节点添加另一个变量之外）的问题在于，它会使算法的时间复杂度从 O(n) 跃升至 O(n^2)。

Answer 3

这是可能的，但需要一些工作。我将假设使用 C++，并省略 struct node 中的 struct 关键字。

您需要做一些簿记来跟踪“ref”指针。在这里，我将它们转换为原始列表中的数字索引，然后返回新列表中的指针。

node *copy_list(node const *head)
{
    // maps "ref" pointers in old list to indices
    std::map<node const *, size_t> ptr_index;
    // maps indices into new list to pointers
    std::map<size_t, node *>       index_ptr;

    size_t length = 0;
    node       *curn; // ptr into new list
    node const *curo; // ptr into old list

    node       *copy = NULL;

    for (curo = head; curo != NULL; curo = curo->next) {
        ptr_index[curo] = length;
        length++;

        // construct copy, disregarding ref for now
        curn = new node;
        curn->next = copy;
        copy = curn;
    }

    curn = copy;
    for (size_t i=0; i < length; i++, curn = curn->next)
        index_ptr[i] = curn;

    // set ref pointers in copy
    for (curo = head, curn = copy; curo != NULL; ) {
        curn->ref = index_ptr[ptr_index[curo->ref]];

        curo = curo->next;
        curn = curn->next;
    }

    return copy;
}

该算法的运行时间为 O(n lg n)，因为它将所有 n 列表元素存储在 std::map，其插入和检索复杂度为 O(lg n)。可以通过使用哈希表来使其线性化。

注意：未经测试，可能包含错误。