复制链接列表 [英] Copy a linked list

问题描述

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

Node *pHead;

PHEAD 是一个单向链表。在接下来字段指向列表中的下一个元素。在等字段可能指向任何其他元素（可以是previous的一个节点或提前的一个节点）列表或 NULL 。

pHead is a singly linked list. The next field points to the next element in the list. The other field may point to any other element (could be one of the previous nodes or one of the nodes ahead) in the list or NULL.

怎样才能写出复制链表及其连接复制功能？在新的列表中的元素（接下来和等）都不应指向任何元素旧名单。

How does one write a copy function that duplicates the linked list and its connectivity? None of the elements (next and other) in the new list should point to any element in the old list.

推荐答案

创建旧列表中的每个节点的新节点，复制相应的数据，使节点的下一个指针，在新的清单指向他们的继任者新的列表，忘记了等指针暂时。在创建一个新节点时记的节点地址是这样的映射：

Create a new node for every node in the old list, copy the corresponding data and make the next pointer of the nodes in the new list point to their successor in the new list, forgetting the other pointer for time being. At the time of creating a new node remember the mapping of node address something like:

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

在第二遍传在新列表中的每个节点考虑其等指针，并找到其对应的节点地图中的新的列表，并使用它作为这个节点的其他指针（在新的列表节点）。

In the second pass pass for every node in the new list consider its other pointer and find its corresponding node in the new list from the map and use it as the other pointer of this node (node in the new list).

这篇关于复制链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！