Programa C++ 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. 

// C++ program to flatten a multilevel 
// linked list
#include <bits/stdc++.h>
using namespace std;
  
// A Linked List Node
struct Node
{
    int data;
    struct Node *next;
    struct Node *down;
};
  
// Flattens a multi-level linked 
// list depth wise
Node* flattenList(Node* node)
{
    // Base case
    if (node == NULL)
        return NULL;
  
    // To keep track of last visited node
    // (NOTE: This is static)
    static Node *last;
    last = node;
  
    // Store next pointer
    Node *next = node->next;
  
    // If down list exists, process it 
    // first. Add down list as next of 
    // current node
    if (node->down)
       node->next = flattenList(node->down);
  
    // If next exists, add it after the next
    // of last added node
    if (next)
       last->next = flattenList(next);
  
    return node;
}
  
// Utility method to print a 
// linked list
void printFlattenNodes(Node* head)
{
    while (head) 
    { 
    printf("%d ", head->data); 
    head = head->next; 
    } 
     
}
  
// Utility function to create a 
// new node
Node* newNode(int new_data)
{
    Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = new_node->down = NULL;
    return new_node;
}
  
// Driver code
int main()
{
    // Creating above example list
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->down = newNode(7);
    head->next->down->down = newNode(9);
    head->next->down->down->down =  
    newNode(14);
    head->next->down->down->down->down = 
    newNode(15);
    head->next->down->down->down->down->next = 
    newNode(23);
    head->next->down->down->down->down->next->down = 
    newNode(24);
    head->next->down->next = newNode(8);
    head->next->down->next->down = newNode(16);
    head->next->down->next->down->down = 
    newNode(17);
    head->next->down->next->down->down->next = 
    newNode(18);
    head->next->down->next->down->down->next->next = 
    newNode(19);
    head->next->down->next->down->down->next->next->next = 
    newNode(20);
    head->next->down->next->down->down->next->next->next->down = 
    newNode(21);
    head->next->down->next->next = newNode(10);
    head->next->down->next->next->down = newNode(11);
    head->next->down->next->next->next = newNode(12);
  
    // Flatten list and print modified list
    head = flattenList(head);
    printFlattenNodes(head);
  
    return 0;
}

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;
}

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