复制链表

Question

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

Node *pHead;

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

如何编写复制链表及其连通性的复制函数？新列表中的任何元素(next 和 other)都不应指向旧列表中的任何元素。

Answer 1

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

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

在第二遍中，新列表中的每个节点都考虑其other 指针，并从映射中找到新列表中其对应的节点并将其用作other 该节点的指针(新列表中的节点)。