复制每个节点中带有随机链接的链表，每个节点都有一个变量，它随机指向列表中的另一个节点
面试问题：
复制链表，每个节点都有随机链接，每个节点有一个变量，随机 指向列表中的另一个节点。
我的想法：
迭代列表，通过其变量复制每个节点及其指向的节点，并在末尾添加一个哨兵，然后对每个节点执行相同的操作。
在新列表中，对于每个节点 i，将每个以哨兵结尾的列表分开，并使用 i 的变量指向它。
它在空间上效率不高。时间和空间上都是O(n^2)。 更好的想法？
An interview question:
copy linked list with random link in each node, each node has a variable，which randomly
points to another node in the list.
My ideas:
Iterate the list, copy each node and its pointed nodes by its variable and add a sentinel at the end and then do the same thing for each node.
In the new list, for each node i, separate each list ended with sentinel and use i's variable points to it.
It is not efficient in space. It is O(n^2) in time and space.
Better ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为你可以从 Java 中汲取灵感
序列化，它可以识别指针何时指向已经序列化的节点，以便它可以合理有效地序列化（然后反序列化）任意结构。该规范，您可以通过 http: //docs.oracle.com/javase/1.4.2/docs/guide/serialization/index.html，说这已经完成，但没有具体说明如何完成 - 我怀疑哈希表。
我认为复制很像这样——你甚至不需要知道某些指针组成了一个链表。您可以使用深度优先搜索来遍历由节点及其指针形成的图，将每个节点的位置以及复制的节点的值放入哈希表中。如果该节点已经存在，则除了使复制节点中的指针指向哈希表所指向的节点的副本之外，您不需要执行任何操作。如果该节点尚不存在，则创建副本，将该节点放入哈希表中，并将副本的地址作为其值，然后递归地将节点中的信息及其指针复制到新创建的副本中。
I think you can pinch ideas from e.g. Java
Serialisation, which recognises when pointers point to nodes already serialised, so that it can serialise (and then deserialise) arbitrary structures reasonably efficiently. The spec, which you can download via a link at http://docs.oracle.com/javase/1.4.2/docs/guide/serialization/index.html, says that this is done but doesn't say exactly how - I suspect hash tables.
I think copying is a lot like this - you don't even need to know that some of the pointers make up a linked list. You could use a depth first search to traverse the graph formed by the nodes and their pointers, putting the location of each node in a hash table as you go, with the value the copied node. If the node is already present you don't need to do anything except make the pointer in the copied node point to the copy of the node pointed to as given by the hash table. If the node is not already present, create the copy, put the node in the hash table with the address of the copy as its value, and recursively copy the information in the node, and its pointers, into the newly made copy.
这是一个典型的面试问题。使用谷歌你可以找到很多答案。我认为这是一个有助于理解的链接。但也请阅读评论，正文中有一些错误： 复制带有下一个和仲裁指针的链接列表
This is a typical interview question. You can find many answers by using Google. This is a link I think is good for understanding. But please read the comments too, there are some errors in the main body: Copy a linked list with next and arbit pointer