此链表是比正常linkedlists不同的是，除了下一指针，它也具有指向另一节点除了本身在链表一个其它指针。

有啥深拷贝的最佳方式此LinkedList不破坏原有并没有多余的空间？

我的做法是简单地做一个为O（n ^ 2）循环，但应该有一些更聪明的方式。

解决方案

这实现是完全未经测试，但这个想法是很简单的。

 的#include＆LT; stdlib.h中＆GT;

结构节点{
    结构节点*下一个;
    结构节点*的东西;
    void *的数据;
};

结构节点*副本（结构节点*根）{
    结构节点* I，*Ĵ，* new_root = NULL;

    为（ⅰ=根，J = NULL; I; J = I，I =异＆gt;接着）{
        结构节点* new_node =的malloc（的sizeof（结构节点））;
        如果（！new_node）中止（）;
        如果（j）条J-＆gt;接着= new_node;
        否则new_root = new_node;
        new_node-＆GT;数据= I-＆GT;的数据;
        I-＆GT;数据= new_node;
    }
    如果（j）条J-＆gt;接着= NULL;

    为（ⅰ=根，J = new_root; I; I =异＆gt;接着，J = J =＆gt;接着）
        J-＆GT;什么= I-＆GT;乜＆GT;的数据;

    为（ⅰ=根，J = new_root; I; I =异＆gt;接着，J = J =＆gt;接着）
        I-＆GT;数据= J-＆GT;的数据;

    返回new_root;
}
 

继 - ＆gt;接下来原来的名单上，建立一个新的列表，反映它。裂伤 - ＆GT;数据老列表中的每个节点上，使其指向新的列表及其相应的节点 走过并联两个列表，并使用较早的错位 - ＆GT;数据来找出其中的 - ＆GT;什么已经在新的列表中。 穿行在并行列表和恢复 - ＆GT;数据到原来的状态

请注意，这是3个直线传递，因而其时间为O（n），并且它不使用超出什么是需要创建新的列表中的任何记忆。

this linkedlist is different than normal linkedlists is that besides the next pointer, it also has a other pointer that points to another node except itself in the linkedlist.

so what's the best way to deep copy this linkedlist without destroying the original and no extra space?

My approach was simply doing a O(n^2) loop , but should be some smarter way.

解决方案

This implementation is completely untested, but the idea is very simple.

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

Following ->next on the original list, create a new list that mirrors it. Mangle ->data on each node in the old list to point to its corresponding node in the new list. Walk through both lists in parallel and use the earlier mangled ->data to figure out where the ->what has gone to in the new list. Walk through both lists in parallel and restore ->data to its original condition.

Note that this is 3 linear passes, thus its time is O(n), and it does not use any memory beyond what is needed to create the new list.