一个面试问题：复制链接列表，每个节点都有一个变量，它随机指向另一个节点列表
复制链接列表，在每个节点随机链接，每个节点都有一个变量，它随机地指向列表中的另一个节点。
我的想法：
迭代列表，通过复制其变量中的每个节点及其尖锐的节点，并在结尾处添加一个哨兵，然后做同样的事情对每个节点。
在新列表中，对于每个节点i，将每个列表以sentinel结尾，并使用i的变量指向它。
它在空间效率不高。在时间和空间上是O（n^2）。 更好的想法？
我认为你可以从例如串行化，它识别指针指向已经序列化的节点的时间，以便它可以合理有效地串行化（然后反序列化）任意结构。这个规范，你可以通过链接http://docs.oracle.com/javase/1.4.2/docs/guide/serialization/index.html下载，这说明已经完成，但并没有说明如何 - 我怀疑哈希表。
我认为复制很像这样 - 你甚至不需要知道某些指针组成了一个链表。您可以使用深度优先搜索来遍历由节点及其指针形成的图形，并随时将每个节点的位置放置在散列表中，其值为复制的节点。如果该节点已经存在，则不需要执行任何操作，除非使复制节点中的指针指向散列表所指向的节点的副本。如果该节点尚不存在，则创建该副本，将该副本的地址中的该节点放入散列表中，并递归地将该节点中的信息及其指针复制到新创建的副本中。
这是一个典型的面试问题。您可以使用Google找到许多答案。这是我认为有助于理解的链接。但请阅读评论，主体内容有误：Copy a linked list with next and arbit pointer