在线性时间内复制普通链表显然很简单。使这一点有趣的唯一部分是随机指针。大概是随机，实际上是指它指向同一链接列表中的另一个随机选择的节点。大概的目的是链接列表的副本重新创建完全相同的结构-即，下一个指针创建线性列表，而其他指针引用相同的相对节点（例如，如果随机指针在原始列表的第一个节点上指向原始列表的第五个节点，则重复列表中的随机指针也将指向重复列表的第五个节点。

Copying a normal linked list in linear time is obviously trivial. The only part that makes this interesting is the "random" pointer. Presumably by "random" you really mean that it points to another randomly chosen node in the same linked list. Presumably, the intent is that the copy of the linked list re-create exactly the same structure -- i.e., the 'next' pointers create a linear list, and the other pointers refer to the same relative nodes (e.g., if the random pointer in the first node of the original list pointed to the fifth node in the original list, then the random pointer in the duplicate list would also point to the fifth node of the duplicate list.

在N ² 时间内执行此操作非常简单：首先正常复制列表，忽略随机指针，然后一次遍历原始列表，每个节点遍历再次列出，以找到随机指针所指的列表中的哪个节点（即，您通过 next 指针遍历了多少个节点以找到 next 指针的地址与当前节点的 random 指针的地址相同，然后遍历重复的列表并反向查找-找到N ^th 节点的地址

Doing this in N² time is fairly easy. First duplicate the list normally, ignoring the random pointer. Then walk through the original list one node at a time, and for each node walk through the list again, to find which node of the list the random pointer referred to (i.e., how many nodes you traverse via the next pointers to find a next pointer holding the same address as the random pointer of the current node. Then walk through the duplicate list and reverse that -- find the N^th node's address, and put that into the current node's random pointer.

这是O（N ² ）的原因主要是那些线性搜索正确的节点。为了获得O（N），这些搜索需要使用恒定的复杂度而不是线性复杂度来完成。

The reason this is O(N²) is primarily those linear searches for the right nodes. To get O(N), those searches need to be done with constant complexity instead of linear complexity.

这样做的显而易见的方法是构建哈希表映射原始列表中每个节点的地址到该节点在列表中的位置。然后我们可以建立一个数组，保存新列表中节点的地址。

The obvious way to do that would be to build a hash table mapping the address of each node in the original list to the position of that node in the list. Then we can build an array holding the addresses of the nodes in the new list.

有了这些，固定随机指针非常容易。首先，我们通过 next 指针遍历原始列表，复制节点，并构建通过 next $ c $连接的新列表c>指针，但不考虑随机指针。为此，我们将每个节点的地址和位置插入哈希表，并将新列表中每个节点的地址插入数组。

With those, fixing up the random pointers is pretty easy. First, we walk through the original list via the next pointers, duplicating the nodes, and building our new list connected via the next pointers, but leaving the random pointers alone. As we do that, we insert the address and position of each node into the hash table, and the address of each node in the new list into our array.

完成后，我们将一步步地浏览旧列表和新列表。对于旧列表中的每个节点，我们查看该节点的随机指针中的地址。我们在哈希表中查找与该地址关联的位置，然后获取该位置新列表中节点的地址，并将其放入新列表当前节点的随机指针中。然后我们前进到旧列表和新列表中的下一个节点。

When we're done with that, we walk through the old list and new list in lock-step. For each node in the old list, we look at the address in that node's random pointer. We look up the position associated with that address in our hash table, then get the address of the node in the new list at that position, and put it into the random pointer of the current node of the new list. Then we advance to the next node in both the old and new lists.

完成后，我们丢弃/销毁了哈希表和数组，因为现在，我们的新列表重复了旧列表的结构，并且我们不再需要多余的数据。

When we're done, we throw away/destroy both the hash table and the array, since our new list now duplicates the structure of the old one, and we don't need the extra data any more.