Aplanar una lista vinculada multinivel -- java campo con algorithm campo con linked-list camp codereview Relacionados El problema

Flatten a multilevel linked list


6
vote

problema

Español

ingrese la descripción de la imagen aquí

Dada tal estructura, la salida debe ser

  10->5->12->7->11->4->20->13->17->6->2->16->9->8->3->19->15.   

Dada una lista vinculada donde además del siguiente puntero, cada nodo tiene un puntero para niños, que puede o no apuntar a una lista separada. Estas listas de niños pueden tener uno o más niños propios, y por lo tanto en, para producir una estructura de datos multinivel, como se muestra a continuación Figura. Usted recibe la cabeza del primer nivel de la lista. Aplanar La lista para que todos los nodos aparezcan en una lista vinculada de un solo nivel. Necesita aplanar la lista de manera que todos los nodos al primer nivel debe venir primero, luego los nodos del segundo nivel, y así sucesivamente.

Esta pregunta se atribuye a GeekForgeeks. Buscando el código-revisión, optimizaciones y mejores prácticas. Verificación de la complejidad para ser $ O (n) $, donde $ N $ es el recuento de todos los nodos en la lista de enlaces multinivel de entrada.

  class Nodes<T> {     Nodes<T> right;     T item;     Nodes<T> down;      Nodes(T item) {         this.item = item;     } }  public final class FlattenMultiLevelList<T> {       public static <T> List<T> flatten (Nodes<T> node) {         final List<T> flattenedList = new ArrayList<>();         final Queue<Nodes<T>> nodeHead = new LinkedList<>();         nodeHead.add(node);          // travese the all heads         while (!nodeHead.isEmpty()) {             Nodes<T> currNode = nodeHead.poll();             // traverse all Linkedlists             while (currNode != null) {                 if (currNode.down != null) { nodeHead.add(currNode.down);  }                   flattenedList.add(currNode.item);                 currNode = currNode.right;             }         }          return flattenedList;     } }  public class FlattenMultiLevelListTest {      @Test     public void test() {         // level 1 should contain only a single linkedlist.         Nodes<Integer> node1_1_1 = new Nodes<>(10);         Nodes<Integer> node1_1_2 = new Nodes<>(5);         Nodes<Integer> node1_1_3 = new Nodes<>(12);         Nodes<Integer> node14 = new Nodes<>(7);         Nodes<Integer> node15 = new Nodes<>(11);          node1_1_1.right = node1_1_2;         node1_1_2.right = node1_1_3;         node1_1_3.right = node14;         node14.right = node15;          // level 2, first linkedlist, first node         Nodes<Integer> node2_1_1 = new Nodes<>(4);         Nodes<Integer> node2_1_2 = new Nodes<>(20);         Nodes<Integer> node2_1_3 = new Nodes<>(13);          node2_1_1.right = node2_1_2;         node2_1_2.right = node2_1_3;         node1_1_1.down = node2_1_1;          // level 2, second linkedlist, first node.         Nodes<Integer> node2_2_1 = new Nodes<>(17);         Nodes<Integer> node2_2_2 = new Nodes<>(6);         node2_2_1.right = node2_2_2;         node1_1_3.down = node2_2_1;           Nodes<Integer> node3_1_1 = new Nodes<>(2);         node2_1_2.down = node3_1_1;          Nodes<Integer> node3_2_1 = new Nodes<>(16);         node2_1_3.down = node3_2_1;          Nodes<Integer> node3_3_1 = new Nodes<>(9);         Nodes<Integer> node3_3_2 = new Nodes<>(8);         node3_3_1.right = node3_3_2;         node2_2_1.down = node3_3_1;          Nodes<Integer> node4_1_1 = new Nodes<>(3);         node3_2_1.down = node4_1_1;           Nodes<Integer> node4_2_1 = new Nodes<>(19);         Nodes<Integer> node4_2_2 = new Nodes<>(15);         node4_2_1.right = node4_2_2;         node3_3_1.down = node4_2_1;           assertEquals(Arrays.asList(10,5,12,7,11,4,20,13,17,6,2,16,9,8,3,19,15), FlattenMultiLevelList.flatten(node1_1_1));     }  }   
Original en ingles

enter image description here

Given such a structure the output should be

10->5->12->7->11->4->20->13->17->6->2->16->9->8->3->19->15. 

Given a linked list where in addition to the next pointer, each node has a child pointer, which may or may not point to a separate list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in below figure.You are given the head of the first level of the list. Flatten the list so that all the nodes appear in a single-level linked list. You need to flatten the list in way that all nodes at first level should come first, then nodes of second level, and so on.

This question is attributed to GeekForGeeks. Looking for code-review, optimizations and best practices. Verifying complexity to be \$O(n)\$, where \$n\$ is the count of all the nodes in the input multilevel linked list.

class Nodes<T> {     Nodes<T> right;     T item;     Nodes<T> down;      Nodes(T item) {         this.item = item;     } }  public final class FlattenMultiLevelList<T> {       public static <T> List<T> flatten (Nodes<T> node) {         final List<T> flattenedList = new ArrayList<>();         final Queue<Nodes<T>> nodeHead = new LinkedList<>();         nodeHead.add(node);          // travese the all heads         while (!nodeHead.isEmpty()) {             Nodes<T> currNode = nodeHead.poll();             // traverse all Linkedlists             while (currNode != null) {                 if (currNode.down != null) { nodeHead.add(currNode.down);  }                   flattenedList.add(currNode.item);                 currNode = currNode.right;             }         }          return flattenedList;     } }  public class FlattenMultiLevelListTest {      @Test     public void test() {         // level 1 should contain only a single linkedlist.         Nodes<Integer> node1_1_1 = new Nodes<>(10);         Nodes<Integer> node1_1_2 = new Nodes<>(5);         Nodes<Integer> node1_1_3 = new Nodes<>(12);         Nodes<Integer> node14 = new Nodes<>(7);         Nodes<Integer> node15 = new Nodes<>(11);          node1_1_1.right = node1_1_2;         node1_1_2.right = node1_1_3;         node1_1_3.right = node14;         node14.right = node15;          // level 2, first linkedlist, first node         Nodes<Integer> node2_1_1 = new Nodes<>(4);         Nodes<Integer> node2_1_2 = new Nodes<>(20);         Nodes<Integer> node2_1_3 = new Nodes<>(13);          node2_1_1.right = node2_1_2;         node2_1_2.right = node2_1_3;         node1_1_1.down = node2_1_1;          // level 2, second linkedlist, first node.         Nodes<Integer> node2_2_1 = new Nodes<>(17);         Nodes<Integer> node2_2_2 = new Nodes<>(6);         node2_2_1.right = node2_2_2;         node1_1_3.down = node2_2_1;           Nodes<Integer> node3_1_1 = new Nodes<>(2);         node2_1_2.down = node3_1_1;          Nodes<Integer> node3_2_1 = new Nodes<>(16);         node2_1_3.down = node3_2_1;          Nodes<Integer> node3_3_1 = new Nodes<>(9);         Nodes<Integer> node3_3_2 = new Nodes<>(8);         node3_3_1.right = node3_3_2;         node2_2_1.down = node3_3_1;          Nodes<Integer> node4_1_1 = new Nodes<>(3);         node3_2_1.down = node4_1_1;           Nodes<Integer> node4_2_1 = new Nodes<>(19);         Nodes<Integer> node4_2_2 = new Nodes<>(15);         node4_2_1.right = node4_2_2;         node3_3_1.down = node4_2_1;           assertEquals(Arrays.asList(10,5,12,7,11,4,20,13,17,6,2,16,9,8,3,19,15), FlattenMultiLevelList.flatten(node1_1_1));     }  } 
        

Lista de respuestas

6
 
vote

Lo que tienes aquí es un derecho solo en orden de tu "árbol". Esto significa que tendrá que a FIFO-cola los nodos descubiertos para continuar desde cuando ya no puede atravesar el derecho.

Su código refleja bien esto, pero tengo algunos comentarios, especialmente en relación con el estilo y el nombramiento:

  Thread5  

imo Usted pone demasiado en esta línea a la vez, especialmente cuando su 99887766555443316 no puede leer bien en voz alta.

Hago esto como un cheque de cordura para mis nombres de variables:
Léalos en voz alta , cuando no puede el nombre es espantoso,
Cuando suena tonto, el nombre es malo,
Y solo cuando puede leer su nombre de variable completo, sin sonar checo, sus nombres son buenos.

De acuerdo con esa "Política", cambiaría el nombre Thread7 a Thread8 o incluso mejor 99887776655443319 .

Algo similar va para su List0 . Establé como objetivo para mí:

Si alguien (ni siquiera programador) puede leer el nombre, y al instante, decir qué hace la variable, clase, interfaz [...], es bueno. Si un programador puede leer el nombre y decirle al instante, es aceptable, todos los demás nombres están sujetos a cambiar de nombre.

Si no le habías proporcionado el gráfico agradable, no tendría ni idea de lo que hace List1 .
Cambiaría el nombre de List2 o algo similar.

Adicionalmente para los puntos ya hechos. I Personalmente Prefiero tener bloques separados.
El código desde arriba se convierte en:

  List3  

Con solo estos dos refuerzos, un poco de estilo y los comentarios eliminados, su método de aplanado se convierte en:

  List4  

Este código IMO es más obvio en su intención y comportamiento.

Si lo tengo bien, entonces esto es de hecho, $ O (N) $ complejidad.

 

What you have here is a right-only in order traversal of your "tree". This means you will have to FIFO-Queue the discovered down nodes to continue from, when you can't traverse right anymore.

Your code nicely reflects this, but I have some comments, especially concerning style and naming:

if (currNode.down != null) { nodeHead.add(currNode.down);  }  

IMO you put too much in this line at once, especially when your currNode cannot be nicely read out loud.

I do this as a sanity check for my variable names:
read them out loud, when you can't the name is gruesome,
when it sounds silly, the name is bad,
and only when you can read your complete variable name, without sounding Czech, your names are good.

In accordance to that "policy" I'd rename currNode to currentNode or even better traversalNode.

Something similar goes for your nodeHead. I set as a goal for myself:

If anybody (not even programmer) can read the name, and instantly tell what the variable, class, interface [...] does, it's good. If a programmer can read the name and instantly tell, it's acceptable, all other names are subject to renaming.

If you hadn't provided the nice graphic, I'd have no clue what nodeHead does.
I'd rename to remainingTraversalHeads or something similar.

Additionally to already made points I personally prefer having blocks separate.
The code from above becomes:

if (traversalNode.down != null) {     remainingTraversalHeads.add(traversalNode.down); } 

With just these two renames, a little styling and the comments removed, your flatten method becomes:

public static <T> List<T> flatten(Nodes<T> node) {     final List<T> flattenedList = new ArrayList<>();     final Queue<T> remainingTraversalHeads = new LinkedList<>();     remainingTraversalHeads.add(node);      while (!remainingTraversalHeads.isEmpty()) {         Nodes<T> traversalNode = remainingTraversalHeads.poll();         while (traversalNode != null) {             if (traversalNode.down != null) {                  remainingTraversalHeads.add(traversalNode.down);             }             flattenedList.add(traversalNode.item);             traversalNode = traversalNode.right;         }     }     return flattenedList; } 

This code IMO is more obvious in it's intention and behaviour.

If I got it right, then this is in fact \$O(n)\$ complexity.

 
 
2
 
vote

@ Vogel612 ha cubierto bastante todo.

El único cambio que haría es agregar comentarios con respecto a los parámetros de entrada y salida ...

y cambiaría el nombre del argumento de List5 a List6 List7 porque no solo quieres ningún nodo, quieres el Nodo de cabeza para que pueda aplanar la lista completa. Cualquier nodo que no está bajo el nodo suministrado no se aplero.

 

@Vogel612 has pretty much got everything covered.

The only change I'd make is to add commentary with regards to input and output parameters...

And I'd rename the argument from node to headNode or head because you don't just want any node, you want the head node so you can flatten the entire list. Any nodes not under the supplied node wouldn't get flattened.

 
 

Relacionados problema

7  Simulando una lista enlazada lineal usando una matriz  ( Simulating a linear linked list using an array ) 
Un programa para simular una lista enlazada lineal usando una matriz: Especificaciones: A Y: cree un nuevo nodo con el valor de datos y, y agregue este...

1  DEQUEUE () en la implementación de la cola que utiliza una lista circular vinculada  ( Dequeue in queue implememtation that uses a circular linked list ) 
Utilizo una lista de enlaces circulares para implementar un queue , y solo sostiene un 99887776665544332 (Tenga en cuenta que 99887776655443333 enlaces a...

14  Implementando una lista relacionada adecuada para un entorno profesional  ( Implementing a proper linked list for a professional environment ) 
Tengo algunas preocupaciones: ¿Es normal que la clase tenga al menos un nodo? En otras palabras, esta implementación no puede tener una lista vinculada va...

4  Eliminar nodos alternativos de una lista vinculada  ( Delete alternate nodes of a linked list ) 
Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4 entonces la salida debe ser 1- & gt; 3. Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4- & gt; 5,...

3  Lista doblemente vinculada en óxido usando los punteros crudos  ( Doubly linked list in rust using raw pointers ) 
Estoy practicando la oxidación escribiendo una lista doblemente vinculada usando los punteros crudos, 9988776655544330 Para asignar datos en el montón, 998...

10  Lista vinculada de objetos de conejito  ( Linked list of bunny objects ) 
El ejercicio es el ejercicio de la lista de conejitos vinculados; El último ejercicio para principiantes de aquí . Estoy buscando comentarios sobre absolut...

5  Cola de bloqueo con la exactitud de la lista doblemente vinculada  ( Lock free queue with doubly linked list correctness ) 
Necesito una cola de bloqueo que se implementa mediante la lista doblemente vinculada. es mi código correcto? ¿Hay algún error? ¿Hay alguna mejoras a realiz...

0  Agregando dos números extremadamente grandes usando una estructura de datos personalizada  ( Adding two extremely large numbers using a custom data structure ) 
Tengo una implementación para agregar 2 números extremadamente grandes, mayor que el techo proporcionado por long , por ejemplo, 1238913893838383813813813813...

5  Destructor para una lista vinculada  ( Destructor for a linked list ) 
El código completo se encuentra aquí: https://gist.github.com/4521540 < / p> Es un maniquí List en C ++. Mi preocupación es para liberar la memoria. No s...

4  ADT Pila con Linkedlist  ( Adt stack with linkedlist ) 
Actualmente estoy preparando para mi examen y estoy tratando de implementar algunos tipos de datos abstractos con listas vinculadas como preparación para el e...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos