复制链接列表

Question

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

Node *pHead;

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

如何编写复制链接列表及其连接的复制功能？新列表中的元素(next和other)都不应指向旧列表中的任何元素.

Answer 1

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

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

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

Answer 2

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

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

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