Descripción de la tarea Se proporciona una lista enlazada de longitud de modo que cada nodo contiene un puntero aleatorio adicional, que podría apuntar a cualquier nodo de la lista, o . n null Construya una de la lista. La copia profunda debe constar de exactamente nodos , donde cada nuevo nodo tiene su valor establecido en el valor de su nodo original correspondiente. Tanto el puntero como el 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. . copia profunda n completamente nuevos next random Ninguno de los punteros de la nueva lista debe apuntar a los nodos de la lista original Por ejemplo, si hay dos nodos e en la lista original, donde , entonces para los dos nodos correspondientes en la lista copiada, . X Y X.random --> Y x 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 nodos. Cada nodo se representa como un par de donde: n [val, random_index] : un número entero que representa val Node.val : el índice del nodo (rango de a ) al que apunta el puntero , o si no apunta a ningún nodo. random_index 0 n-1 random null Su código se le dará el de la lista enlazada original. solo head 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 es o apunta a algún nodo en la lista vinculada. Node.random null 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. Necesitamos crear una copia de cada nodo con el mismo valor que el original. Necesitamos establecer punteros al siguiente nodo de la misma manera que en el original 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í
