Cree una copia duplicada de la lista vinculada en O (n) tiempo

Se proporciona una lista de enlaces con dos punteros, el primero apunta al siguiente nodo y otro es un puntero aleatorio. El puntero aleatorio está apuntando a cualquier nodo de LinkedList. Escriba un progtwig completo para crear una copia de la Lista vinculada (c, c ++, c #), sin cambiar la lista original y en O (n).

Me hicieron esta pregunta en una de las entrevistas y no pude encontrar la solución. La ayuda sería apreciada.

Copiar una lista enlazada normal en tiempo lineal es obviamente trivial. La única parte que hace esto interesante es el puntero “aleatorio”. Presumiblemente, por “aleatorio”, realmente quiere decir que apunta a otro nodo elegido al azar en la misma lista vinculada. Presumiblemente, la intención es que la copia de la lista enlazada vuelva a crear exactamente la misma estructura; es decir, los punteros ‘siguientes’ crean una lista lineal, y los otros punteros se refieren a los mismos nodos relativos (por ejemplo, si el puntero aleatorio en el primer nodo de la lista original apuntada al quinto nodo en la lista original, entonces el puntero aleatorio en la lista duplicada también apuntaría al quinto nodo de la lista duplicada.

Hacer esto en N 2 es bastante fácil. Primero duplica la lista normalmente, ignorando el puntero aleatorio. Luego recorra la lista original un nodo a la vez y, para cada nodo, vuelva a recorrer la lista para encontrar a qué nodo de la lista se refiere el puntero aleatorio (es decir, cuántos nodos atraviesa los next punteros para encontrar un next puntero que contiene la misma dirección que el puntero random del nodo actual. Luego recorra la lista de duplicados e invierta eso: busque la dirección del nodo N th , y póngala en el puntero aleatorio del nodo actual.

La razón por la que esto es O (N 2 ) es principalmente aquellas búsquedas lineales para los nodos correctos. Para obtener O (N), esas búsquedas deben realizarse con complejidad constante en lugar de complejidad lineal.

La forma obvia de hacerlo sería crear una tabla hash que asigne la dirección de cada nodo en la lista original a la posición de ese nodo en la lista. Luego podemos construir una matriz que contenga las direcciones de los nodos en la nueva lista.

Con eso, arreglar los punteros al azar es bastante fácil. Primero, recorremos la lista original a través de los next punteros, duplicando los nodos y construyendo nuestra nueva lista conectada a través de los next punteros, pero dejando solo los punteros aleatorios. Mientras lo hacemos, insertamos la dirección y la posición de cada nodo en la tabla hash y la dirección de cada nodo en la nueva lista en nuestra matriz.

Cuando hayamos terminado con eso, repasamos la lista anterior y la nueva en Lock-Step. Para cada nodo en la lista anterior, observamos la dirección en el puntero aleatorio de ese nodo. Buscamos la posición asociada con esa dirección en nuestra tabla hash, luego obtenemos la dirección del nodo en la nueva lista en esa posición y la colocamos en el puntero aleatorio del nodo actual de la nueva lista. Luego avanzamos al siguiente nodo tanto en la lista antigua como en la nueva.

Cuando hayamos terminado, desechamos / destruimos tanto la tabla hash como la matriz, ya que nuestra nueva lista ahora duplica la estructura de la anterior, y ya no necesitamos los datos adicionales.

Visión general del enfoque
No intentaremos crear una nueva lista enlazada desde el principio. Duplique primero los elementos en la lista vinculada original, luego divida la lista en 2 listas idénticas.

Los detalles
Paso 1 : ejecute la lista enlazada utilizando los siguientes punteros y cree un duplicado de cada nodo.

 original :: A -> B -> C -> D -> E ->null updated :: A -> A' -> B -> B' -> C -> C' -> D -> D' ->E -> E' -> null 

Esto se puede hacer fácilmente en un solo bucle.

Paso 2 : recorre la lista de nuevo y corrige los punteros aleatorios como este

 Node *current= start; Node *newListNode, *random; while (current!= null) { // If current node has a random pointer say current = A, A.random = D; if ( (*current)->random != null ) { // newListNode will point to A' newListNode = (*current)->next; random = (*current)->random; random = (*random)->next; // Make A' point to D's next, which is D' (*newListNode)->random = random; } // Here A'.random = D' // Current goes to the next node in the original list => B , and not A' current= (*newListNode)->next; } 

Paso 3 :: Divide la lista en 2 listas. Solo necesitas arreglar los siguientes punteros aquí.

 Original :: A -> A' -> B -> B' -> C -> C' -> D -> D' ->E -> E' -> null New :: A -> B -> C -> D -> E ->null A' -> B' -> C' -> D' -> E' ->null Node *start1 = head; Node *start2 = (*head) ->next // Please check the boundary conditions yourself, // I'm assuming that input was a valid list Node *next, *traverse = start2; while (traverse != null) { next = (*traverse)->next; if (next == null) { (*traverse)->next = null; break; } (*traverse)->next = (*next)->next; traverse = next; } 

De esta manera, ha creado una copia de la lista original en O (n) tiempo. Atraviesas la lista 3 veces, lo que sigue siendo el orden de n.

Aclarando edición:

Lo siguiente funciona solo si los punteros “aleatorios” son únicos, como lo señaló BowieOwens.
Dejo la respuesta solo por la idea general, pero por favor, no voten, ya que definitivamente está mal .


Si no estoy completamente equivocado, puedes hacerlo sin utilizar ningún almacenamiento adicional.

Cuando esté copiando la lista anterior, almacene el puntero random del nodo anterior en el puntero random del nuevo nodo.
A continuación, establezca el puntero random del nodo antiguo para que apunte al nuevo nodo.

Esto le dará una estructura de “zig-zag” entre la lista anterior y la nueva lista.

Pseudocódigo

 Node* old_node = ; Node * new_node = new Node; new_node->random = old_node->random; old_node->random = new_node; 

Una vez que haya copiado la lista anterior de esa manera, comience de nuevo, pero reemplace los punteros random esta manera, restaurando los punteros en la lista antigua mientras establece los punteros random en la nueva lista a los nuevos nodos correspondientes:

 Node* old_random = old_node->random->random; // old list -> new list -> old list Node* new_random = new_node->random->random; // new list -> old list -> new list old_node->random = old_random; new_node->random = new_random; 

Se ve mucho mejor en el papel, pero me temo que mis habilidades artísticas de ASCII no están a la altura.

Esto cambia la lista original, pero se restaura al estado original.
Si eso es permisible depende de la entrevista, supongo.

Como debes saber, O (n) significa lineal. Como necesita una copia de una estructura de datos lineal, no tendrá problemas con ella, ya que solo necesita recorrer los nodos de la lista original y, para cada nodo visitado, creará un nuevo nodo para la nueva lista. Creo que la pregunta no está bien formulada, porque necesita conocer algunos aspectos para hacer el trabajo, ya que: ¿esto es una implementación circular? ¿Qué es el “siguiente” nodo? ¿El siguiente nodo de un nodo o el primer nodo de la lista? ¿Cómo termina la lista?

Tal vez esta pregunta sea un truco, para probar cómo respondes a una pregunta extraña, porque es muy simple:

1) Iterar a cada nodo

2) Cree un nuevo nodo para otra lista vinculada y copie el valor.

El costo siempre es O (n): ¡¡¡porque solo iterarás a la lista de enlaces completa solo por 1 vez !!!

O bien, has entendido algo mal en su pregunta.