Aplanar una lista enlazada de varios niveles | Conjunto 2 (Profundidad sabia)

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 de forma recursiva 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. 

Bloque de código

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

Node* flattenList2(Node* head)
{
    Node* headcop = head;
    stack<Node*> save;
    save.push(head);
    Node* prev = NULL;
 
    while (!save.empty()) {
        Node* temp = save.top();
        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;
}

Node flattenList2(Node head)
{
    Node headcop = head;
    Stack<Node> save = new Stack<>();
    save.push(head);
    Node prev = null;
 
    while (!save.isEmpty()) {
        Node temp = save.peek();
        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 contributed by aashish1995

def flattenList2(head):
 
    headcop = head
    save = []
    save.append(head)
    prev = None
  
    while (len(save) != 0):
        temp = save[-1]
        save.pop()
  
        if (temp.next):
            save.append(temp.next)
        if (temp.down):
            save.append(temp.down)
  
        if (prev != None):
            prev.next = temp
  
        prev = temp
     
    return headcop
 
# This code is contributed by rutvik_56

Node flattenList2(Node head)
{
    Node headcop = head;
    Stack<Node> save = new Stack<Node>();
    save.Push(head);
    Node prev = null;
 
    while (!save.Count != 0)
    {
        Node temp = save.Peek();
        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>
    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 contributed by aashish1995
</script>

Este artículo es una contribución de Mu Ven . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.