java - 如何创建保持相同顺序的链接列表的深拷贝

Question

我在求职面试中被问到以下问题，我无法弄清楚。您将获得以下节点元素的链接列表:

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

循环所有节点并将所有节点放入 HashMap 中，节点作为键，新的节点实例作为值。

Map<Node, Node> nodeMap = new HashMap<>();
...
nodeMap.put(currentNode, new Node();

现在您再次通过遍历 node.next 来遍历所有“旧”节点，并为每个节点复制节点，以便您引用 map 的值而不是旧节点本身。

Node newNode = nodeMap.get(currentNode);
newNode.value = currentNode.value;
newNode.next = nodeMap.get(currentNode.next);
newNode.random = nodeMap.get(currentNode.random);

之后你应该有一个没有重复实例的精确副本。