java - 克隆单链表

Question

我有一个单链表。除了正常的“Next”指针外，每个节点中还有一个指针（随机 ptr）指向列表中的某个随机节点。如何创建这样一个列表的克隆？（小于 O(n^2)）。

使用 Java 的任何建议或解决方案？

Answer 1

您可以按顺序克隆所有节点，并在第一次通过时，构建一个身份映射，将每个原始节点与其克隆相关联。

然后做第二遍，对于每个原始节点，获取其关联的随机节点，然后从映射中获取对应的克隆，并将原始节点的克隆与随机节点的克隆相关联。整个过程仍然是 O(n)。

Answer 2

可以有两种方法：

1）散列所有节点的地址，并存储随机指针指向的节点。（总体复杂度为O(n).）

2）另一个O（n）解决方案将如链接所示（不使用任何额外空间）：http ://www.geeksforgeeks.org/archives/1155

Answer 3

这是 O(n) 时间和 O(1) 空间的答案。（具有哈希表或关联映射的解决方案需要 O(n) 空间）。shg的链接也是O(n)时间和O(1)空间的解。

• 遍历列表以计算单元格的数量，n。
• 创建一个大小为 n 的数组t，每个单元由两个指针a和组成b。在算法结束时，这将是副本。但现在不是。
• 遍历原始列表。对于原始列表 的k^{第 th 个}单元格：c
  • 让t[k].a成为一个指针 c
  • letc.next是一个指向的指针t[k]（原来的列表暂时被破坏了，我们稍后会恢复它。）。我们现在可以在原始列表和t.
• 遍历原始列表，对于每个单元格c，让c.next.b是指向 的指针c.random.next。（c.next是 中的一个单元格t，所以也是c.random.next）。这样，b单元格的字段是原始列表中指针t结构的副本。random
• 恢复原始列表：对于每个k，让t[k].a.next指向t[k+1].a.next
• 制作t一个链表：对于每个k，让t[k].a指向t[k+1]。

与 shg 的链接相反，此解决方案的缺点是需要内存中大小为 n 的连续块。

Answer 4

列表中的每个节点都有两个引用：“下一个”和“随机”。假设“随机”总是引用前一个。你得到双链表。在不失一般性的情况下，您可以将克隆双链表的过程应用于克隆您的列表。检查这个SO answer 他们如何克隆 DL 列表。复杂度应该是 O(n)。