如何创建保持相同顺序的链表的深层副本

Question

我在求职面试中被问到以下问题，但我无法弄清楚。您将获得以下 Node 元素的链表：

class Node {
  int value;
  Node next; // points to next element in list
  Node random; // points to one random element of list
}

假设您有这些节点的链表（比如 20 个节点），其中“next”指向下一个元素，“random”指向列表的另一个元素（意思是，可以指向列表中一个特定但随机选择的元素））。即，第一个元素的“随机”可以指向节点#5，节点第二个元素的随机可以指向节点#9，等等。

问题：你如何创建一个全新的链表，它是这个节点列表的深层副本，但为“随机”和“下一个”保持相同的顺序和链接？

换句话说，如果使用这两个指针中的任何一个遍历这个新列表，遍历的顺序将是相同的。

一些人引用的另一个主题将通过默认克隆克隆相同的指针，这不会解决这个挑战。

Answer 1

在网上搜索了一段时间后，我找到了这个问题的答案。相当棘手。他们提出了这个主要解决方案：