克隆单向链表

Question

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

有没有使用Java的任何建议或解决方法？

- user1920811

---

你好！随机节点是否属于常规列表？因此，所有随机节点都指向列表中的某个位置，还是它们指向一些真正随机的内容？ - Balázs Édes

@bali182：这个问题说：每个节点中都有一个额外的指针（随机 ptr），它指向链表中的某个随机节点。 - JB Nizet

Answer 1

您可以按顺序克隆所有节点，并在此第一遍遍历期间构建一个身份映射，将每个原始节点与其克隆体关联起来。

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

- JB Nizet

Answer 2

有两种方法：

1）对所有节点的地址进行哈希，并存储随机指针指向的节点。 （总体复杂度为O（n）。）

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

- Rndm

Answer 3

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

• 遍历列表以计算单元格数量n。
• 创建大小为n的数组t，每个单元格包含两个指针a和b。在算法结束时，这将是副本。但现在还不是。
• 遍历原始列表。对于原始列表的第k个单元格c：
  • 让t[k].a成为指向c的指针
  • 让c.next成为指向t[k]的指针（原始列表暂时被破坏，稍后我们将恢复它）。现在我们可以在原始列表和t之间来回跟随指针。
• 遍历原始列表，并对于每个单元格c，让c.next.b成为指向c.random.next的指针。（c.next是t中的一个单元格，因此也是c.random.next）。这样，t中单元格的b字段是原始列表中random指针结构的副本。
• 恢复原始列表：对于每个k，让t[k].a.next指向t[k+1].a.next
• 使t成为链接列表：对于每个k，让t[k].a指向t[k+1]。

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

- jrouquie

Answer 4

你的列表中每个节点都有两个引用："Next"和"Random"。假设"Random"总是指向前一个节点。你得到了一个双向链表。不失一般性，你可以将双向链表克隆的过程应用于克隆你的列表。请查看this这个SO答案，了解他们如何克隆双向链表。复杂度应该为O(n)。

- mishadoff

---

除非随机指针指向前一个节点，否则如果它指向列表中后面175个位置的节点，算法就无法应用，因为您尚未克隆该节点。 - JB Nizet