Programa Javascript para aplanar una lista enlazada de varios niveles Profundidad Wise-Set 2

Hemos discutido el aplanamiento de una lista enlazada de varios niveles donde los Nodes tienen dos punteros hacia abajo y hacia adelante. En la publicación anterior, aplanamos la lista vinculada por niveles. Cómo aplanar una lista enlazada cuando siempre necesitamos procesar el puntero hacia abajo antes del siguiente en cada Node.

Input:  
1 - 2 - 3 - 4
    |
    7 -  8 - 10 - 12
    |    |    |
    9    16   11
    |    |
    14   17 - 18 - 19 - 20
    |                    |
    15 - 23             21
         |
         24

Output:        
Linked List to be flattened to
1 - 2 - 7 - 9 - 14 - 15 - 23 - 24 - 8
 - 16 - 17 - 18 - 19 - 20 - 21 - 10 - 
11 - 12 - 3 - 4
Note: 9 appears before 8 (When we are 
at a node, we process down pointer before 
right pointer)

Fuente: Entrevista de Oracle

Si observamos más de cerca, podemos notar que este problema es similar a la conversión de árbol a lista enlazada . Aplanamos recursivamente una lista enlazada con los siguientes pasos:

1. Si el Node es NULL, devuelve NULL.
2. Almacene el siguiente Node del Node actual (usado en el paso 4).
3. Aplanar recursivamente la lista. Mientras aplana, realice un seguimiento del último Node visitado, de modo que la siguiente lista pueda vincularse después de él. 
4. Aplane recursivamente la siguiente lista (obtenemos la siguiente lista del puntero almacenado en el paso 2) y la adjuntamos después del último Node visitado.

A continuación se muestra la implementación de la idea anterior. 

<script>
// Javascript program to flatten 
// a multilevel linked list
  
// Node of Multi-level Linked List
class Node 
{
    constructor(val) 
    {
        this.data = val;
        this.down = null;
        this.next = null;
    }
}
var last;
  
// Flattens a multi-level linked
// list depth wise
function flattenList(node) 
{
    if (node == null)
        return null;
  
    // To keep track of last visited 
    // node
    // (NOTE: This is )
    last = node;
  
    // Store next pointer
    var next = node.next;
  
    // If down list exists, process it 
    // first. Add down list as next of 
    // current node
    if (node.down != null)
        node.next = flattenList(node.down);
  
    // If next exists, add it after the next
    // of last added node
    if (next != null)
        last.next = flattenList(next);
  
    return node;
}
  
// Utility method to print a linked list
function printFlattenNodes(head) 
{
    var curr = head;
    while (curr != null) 
    {
        document.write(curr.data + " ");
        curr = curr.next;
    }
}
  
// Utility function to create a 
// new node
function push(newData) 
{
    var newNode = new Node(newData);
    newNode.next = null;
    newNode.down = null;
    return newNode;
}
  
// Driver code
var head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.down = new Node(7);
head.next.down.down = new Node(9);
head.next.down.down.down = new Node(14);
head.next.down.down.down.down = 
new Node(15);
head.next.down.down.down.down.next =
new Node(23);
head.next.down.down.down.down.next.down = 
new Node(24);
head.next.down.next = 
new Node(8);
head.next.down.next.down = 
new Node(16);
head.next.down.next.down.down = 
new Node(17);
head.next.down.next.down.down.next = 
new Node(18);
head.next.down.next.down.down.next.next = 
new Node(19);
head.next.down.next.down.down.next.next.next = 
new Node(20);
head.next.down.next.down.down.next.next.next.down = 
new Node(21);
head.next.down.next.next = new Node(10);
head.next.down.next.next.down = new Node(11);
head.next.down.next.next.next = new Node(12);
head = flattenList(head);
printFlattenNodes(head);
// This code is contributed by aashish1995 
</script>

Producción: 

1 2 7 9 14 15 23 24 8 16 17 18 19 20 21 10 11 12 3 4

Implementación alternativa usando la estructura de datos de pila

<script>
function flattenList2(head)
{
    var headcop = head;
    var save = new Stack();
    save.push(head);
    var prev = null;
  
    while (!save.isEmpty()) 
    {
        var temp = save.pop();    
  
        if (temp.next)
            save.push(temp.next);
        if (temp.down)
            save.push(temp.down);
        if (prev != null)
            prev.next = temp;
  
        prev = temp;
    }
    return headcop;
}
// This code is contributed by aashish1995 
</script>

Consulte el artículo completo sobre
Aplanar una lista enlazada de varios niveles | Conjunto 2 (Profundidad sabia)
¡para más detalles!