一個面試問題：複製鏈接列表，每個節點都有一個變量，它隨機指向另一個節點列表
複製鏈接列表，在每個節點隨機鏈接，每個節點都有一個變量，它隨機地指向列表中的另一個節點。
我的想法：
迭代列表，通過複製其變量中的每個節點及其尖銳的節點，並在結尾處添加一個哨兵，然後做同樣的事情對每個節點。
在新列表中，對於每個節點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