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í

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Coding

2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Coding

Este audio es producido en el idioma original de la historia!

Algoritmos de Java: lista de copia con puntero aleatorio (LeetCode)

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

Valhalla de Floki se une como patrocinador asociado de la gira de la India por Sri Lanka

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

La guía completa para una migración exitosa a la nube: estrategias y mejores prácticas

Valhalla de Floki se une como patrocinador asociado de la gira de la India por Sri Lanka

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

La guía completa para una migración exitosa a la nube: estrategias y mejores prácticas

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps