复制链接列表
typedef struct Node { int data; Node *next; Node *other; }; Node *pHead;
pHead
是一个单独的链表。 next
字段指向列表中的下一个元素。 other
字段可以指向列表中的任何其他元素(可以是先前节点之一或前面的一个节点)或NULL
。
如何编写复制链接列表及其连接的复制function? 新列表中的所有元素( next
和other
元素)都不应指向旧列表中的任何元素。
为旧列表中的每个节点创建一个新节点,复制相应的数据,并使新列表中节点的下一个指针指向新列表中的后继节点,暂时忘记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的解决方案,但这将是我的答案:
-
迭代链表。
一个。 将数据存储在一个数组中(当然,第i个节点的位置i)
湾 用i替换数据来创建一个id(这样你肯定知道你在说哪个节点) -
创建第一个大小的第二个链表(暂时忽略其他指针)*。 也许使用临时数组来快速找到每个节点
-
迭代第一个链表。 一个。 找出其他指向哪个id(在该节点数据中)b。 在第二个链接列表中重新创建此链接(临时数组可能真的有帮助)
-
同时迭代两个链表并用存储的数据替换数据中的ID
当然你可以在这里崩溃一些处理和迭代。 但这大致是我想要做的。