Descripción de la tarea

Se proporciona una lista enlazada de longitud n de modo que cada nodo contiene un puntero aleatorio adicional, que podría apuntar a cualquier nodo de la lista, o null .

Construya una copia profunda de la lista. La copia profunda debe constar de exactamente n nodos completamente nuevos , donde cada nuevo nodo tiene su valor establecido en el valor de su nodo original correspondiente. Tanto el puntero next como el random de los nuevos nodos deben apuntar a nuevos nodos en la lista copiada de modo que los punteros en la lista original y la lista copiada representen el mismo estado de lista. Ninguno de los punteros de la nueva lista debe apuntar a los nodos de la lista original .

Por ejemplo, si hay dos nodos X e Y en la lista original, donde X.random --> Y , entonces para los dos nodos correspondientes x en la lista copiada, y x.random --> y .

Devuelve el encabezado de la lista enlazada copiada .

La lista enlazada se representa en la entrada/salida como una lista de n nodos. Cada nodo se representa como un par de [val, random_index] donde:

• val : un número entero que representa Node.val

• random_index : el índice del nodo (rango de 0 a n-1 ) al que apunta el puntero random , o null si no apunta a ningún nodo.

  
  

Su código solo se le dará el head de la lista enlazada original.

Ejemplo 1:

 Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Ejemplo 2:

 Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]

Ejemplo 3:

 Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]

Restricciones:

• 0 <= n <= 1000
• -104 <= Node.val <= 104
• Node.random es null o apunta a algún nodo en la lista vinculada.

Razonamiento:

A primera vista, esta tarea parece difícil, aunque en realidad no lo es. Pero tiene una propiedad a la que debemos prestar atención y crear un hábito a su alrededor. Cada vez que vea un problema que se puede dividir en problemas más pequeños, divídalo. Es uno de los patrones esenciales que puede aplicar a casi cualquier problema. Déjame ayudarte con esto. Volvamos a leer la tarea nuevamente y dividámosla en subproblemas más pequeños.

1. Necesitamos crear una copia de cada nodo con el mismo valor que el original.

2. Necesitamos establecer punteros al siguiente nodo de la misma manera que en el original

3. Necesitamos establecer punteros al nodo aleatorio de la misma manera que en el one+ original

   
   

Puede decir en este punto, espere en lugar de tener un problema ahora tenemos 3. Sí, tiene razón, pero son mucho más fáciles de resolver. Pasemos a la sección de soluciones y te lo probaré.

Requisito previo:

Si desea depurar su código, lo cual recomiendo personalmente, debe introducir esta clase

 class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } }

Solución:

Comencemos por resolver el primer subproblema. Hagamos una iteración simple a través de la lista enlazada y creemos una copia para cada nodo en ella. Elijo HashMap para almacenar pares como nodo antiguo -> nodo nuevo. Siempre que vayamos a iterar desde el principio de la lista hasta el final, introduzcamos también la variable temporal y configúrela para que sea el principio de la lista.

 Map<Node, Node> map = new HashMap<>(); Node temp = head; while (temp != null) { map.put(temp, new Node(temp.val)); temp = temp.next; }

Resolvimos el primer subproblema. Te sorprenderá lo fácil que podemos resolver los siguientes dos. Ya tenemos conexiones entre nodos antiguos y nuevos. Solo necesitamos completar los punteros al siguiente nodo y al puntero aleatorio. Nuestro mapa ya almacena toda la información que necesitamos. Configuremos de nuevo a temp para que sea el encabezado de la lista. También presentemos un nuevo nodo ficticio que almacenará el enlace a nuestro encabezado recién copiado. Lo último que necesitamos es el puntero anterior que nos ayudará a configurar el nodo de relación -> siguiente nodo

Nuestras soluciones deberían verse así.

 public Node copyRandomList(Node head) { Map<Node, Node> map = new HashMap<>(); Node temp = head; while (temp != null) { map.put(temp, new Node(temp.val)); temp = temp.next; } temp = head; Node dummy = new Node(0); Node prev = dummy; while (temp != null) { prev.next = map.get(temp); map.get(temp).random = map.get(temp.random); prev = prev.next; temp = temp.next; } return dummy.next; }

El código anterior nos da una complejidad lineal de tiempo y espacio.

También publicado aquí .