gpt4 book ai didi

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

转载 作者:搜寻专家 更新时间:2023-11-01 03:17:20 26 4
gpt4 key购买 nike

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

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,等等。

问题:如何创建一个全新的链表,它是此节点列表的深拷贝,但对“随机”和“下一个”保持相同的顺序和相同的链接?

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

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

最佳答案

循环所有节点并将所有节点放入 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);

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

关于java - 如何创建保持相同顺序的链接列表的深拷贝,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45093119/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com