复制链接列表

typedef struct Node { int data; Node *next; Node *other; }; Node *pHead; 

pHead是一个单独的链表。 next字段指向列表中的下一个元素。 other字段可以指向列表中的任何其他元素(可以是先前节点之一或前面的一个节点)或NULL

如何编写复制链接列表及其连接的复制function? 新列表中的所有元素( nextother元素)都不应指向旧列表中的任何元素。

为旧列表中的每个节点创建一个新节点,复制相应的数据,并使新列表中节点的下一个指针指向新列表中的后继节点,暂时忘记other指针。 在创建新节点时,请记住节点地址的映射,例如:

 Old_list New_list ------------------- 0x123 0x345 [ addresses of the first node] 0xabc 0xdef [ addresses of the second node] ... 

在新列表中的每个节点的第二次传递中,考虑其other指针,并从映射中的新列表中找到其对应的节点,并将其用作此节点的other指针(新列表中的节点)。

碰到了这个 。 希望能帮助到你!

引用此链接中的一个解决方案,如下所示。

1)创建1的副本并将其插入1和2之间,创建2的副本并将其插入2和3之间。以这种方式继续,将N的副本添加到第N个节点

2)现在以这种方式复制任意链接

  if original->arbitrary is not NULL original->next->arbitrary = original->arbitrary->next; /*TRAVERSE TWO NODES*/ else original->next->arbitrary=NULL; 

这是有效的,因为原始 – >接下来只是原始副本和原始 – >任意 – >接下来只是任意副本。

3)现在以这种方式在单个循环中恢复原始和复制链接列表。

  original->next = original->next->next; copy->next = copy->next->next; 

4)确保original-> next的最后一个元素为NULL。

示例代码,时间复杂度O(N),空间复杂度O(1)

 pNode copy_list(pNode head) { // pre-condition: node->other either points into the list or NULL if (!head) return NULL; pNode node = head, copied = NULL, cnode = NULL; for ( ; node; node = node->next->next) { // make copy cnode = newnode(node->next, node->data); cnode->other = node->other; if (node == head) copied = cnode; // insert the copy between originals node->next = cnode; // node -> cnode -> (orig)node->next } for (node = head; node && node->next; node = node->next->next /* only original nodes */) if (node->other) node->next->other = node->other->next; else node->next->other = NULL; // restore lists node = head; cnode = copied; for ( ; cnode && cnode->next; node = node->next, cnode = cnode->next) { node->next = node->next->next; cnode->next = cnode->next->next; } node->next = NULL; return copied; } 

完整的计划见http://gist.github.com/349630

我喜欢Codaddict的解决方案,但这将是我的答案:

  1. 迭代链表。
    一个。 将数据存储在一个数组中(当然,第i个节点的位置i)
    湾 用i替换数据来创建一个id(这样你肯定知道你在说哪个节点)

  2. 创建第一个大小的第二个链表(暂时忽略其他指针)*。 也许使用临时数组来快速找到每个节点

  3. 迭代第一个链表。 一个。 找出其他指向哪个id(在该节点数据中)b。 在第二个链接列表中重新创建此链接(临时数组可能真的有帮助)

  4. 同时迭代两个链表并用存储的数据替换数据中的ID

当然你可以在这里崩溃一些处理和迭代。 但这大致是我想要做的。