java - ultimo - Cómo crear una copia profunda de la lista vinculada que mantiene el mismo orden
makigas listas (3)
Me hicieron la siguiente pregunta en una entrevista de trabajo que no pude descifrar. Se le proporciona una Lista Vinculada de los siguientes elementos de Nodo:
class Node {
int value;
Node next; // points to next element in list
Node random; // points to one random element of list
}
Supongamos que tiene una lista vinculada de estos nodos (digamos 20 nodos) donde "siguiente" apunta al siguiente elemento y "aleatorio" apunta a otro elemento de la lista (es decir, puede señalar un elemento específico pero elegido al azar en la lista) ) Es decir, el "elemento aleatorio" del 1er elemento puede apuntar al nodo # 5, el nodo al azar del 2 ° elemento puede apuntar al nodo # 9, etc.
Pregunta: ¿Cómo se crea una nueva lista vinculada que es una copia profunda de esta lista de nodos, pero mantiene el mismo orden y los mismos vínculos para "aleatorio" y "siguiente"?
En otras palabras, si uno atraviesa esta nueva lista usando cualquiera de estos 2 indicadores, el orden de recorrido sería el mismo.
El otro tema que algunas personas mencionaron clonaría los mismos punteros a través del clon predeterminado y eso no resolvería este desafío.
Bucle todos los nodos y poner todos los nodos en un HashMap con el nodo como clave y una nueva instancia de nodo como valor.
Map<Node, Node> nodeMap = new HashMap<>();
...
nodeMap.put(currentNode, new Node();
Ahora vuelve a iterar sobre todos sus nodos "antiguos" simplemente recorriendo node.next y para cada nodo copie los nodos de modo que esté haciendo referencia al valor del mapa en lugar del nodo anterior.
Node newNode = nodeMap.get(currentNode);
newNode.value = currentNode.value;
newNode.next = nodeMap.get(currentNode.next);
newNode.random = nodeMap.get(currentNode.random);
Después de eso, debe tener una copia exacta sin instancias duplicadas.
Después de buscar en línea por un tiempo, encontré este problema con una respuesta. Bastante complicado. Presentan esta solución principal:
- copie cada nodo, es decir, duplique cada nodo e insértelo en la lista
- copiar punteros aleatorios para todos los nodos recién creados
- divide la lista en dos
Vea aquí: http://www.programcreek.com/2012/12/leetcode-copy-list-with-random-pointer/