c - 在不破坏原始列表和额外存储空间的情况下深度复制链表(使用 ANSI C)

Question

这个链表与普通链表不同的是，除了next指针外，它还有一个other指针，指向链表中除自身以外的另一个节点。

那么在不破坏原始链表且没有额外空间的情况下深度复制此链表的最佳方法是什么？

我的方法只是简单地执行一个 O(n^2) 循环，但应该是一些更聪明的方法。

Answer 1

此实现完全未经测试，但想法非常简单。

#include <stdlib.h>

struct node {
    struct node *next;
    struct node *what;
    void *data;
};

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 = malloc(sizeof(struct node));
        if (!new_node) abort();
        if (j) j->next = new_node;
        else new_root = new_node;
        new_node->data = i->data;
        i->data = new_node;
    }
    if (j) j->next = NULL;

    for (i = root, j = new_root; i; i = i->next, j = j->next)
        j->what = i->what->data;

    for (i = root, j = new_root; i; i = i->next, j = j->next)
        i->data = j->data;

    return new_root;
}

1. 在原始列表的 ->next 之后，创建一个反射(reflect)它的新列表。 Mangle ->data 在旧列表中的每个节点上指向它在新列表中的相应节点。
2. 并行遍历两个列表，并使用之前损坏的 ->data 找出 ->what 在新列表中的位置。
3. 并行遍历两个列表并将 ->data 恢复到其原始状态。

请注意，这是 3 次线性遍历，因此它的时间是 O(n)，并且它不会使用超出创建新列表所需的任何内存。