复制链表 [英] Copy a linked list

问题描述

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

Node *pHead;

pHead 是一个单向链表.next 字段指向列表中的下一个元素.other 字段可以指向列表中的任何其他元素(可能是前面的节点之一或前面的节点之一)或 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.

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

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.

推荐答案

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

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]
...

在新列表中的每个节点的第二轮传递中，考虑其other 指针，并从地图中找到其在新列表中的对应节点，并将其用作other> 该节点的指针(新链表中的节点).

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屋！