Programa de Python 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. 

# Python3 program to flatten a multilevel 
# linked list
  
# A Linked List Node
class Node:
    def __init__(self, val):
        self.data = val
        self.down = None
        self.Next = None
  
last = None
   
# Flattens a multi-level linked
# list depth wise
def flattenList(node):
    if (node == None):
        return None
  
    # To keep track of last visited 
    # node
    # (NOTE: This is )
    last = node
  
    # Store next pointer
    Next = node.Next
  
    # If down list exists, process it 
    # first. Add down list as next of 
    # current node
    if (node.down != None):
        node.Next = flattenList(node.down)
  
    # If next exists, add it after the
    # next of last added node
    if (Next != None):
        last.Next = flattenList(Next)
  
    return node
  
# Utility method to print a 
# linked list
def printFlattenNodes(head):
    curr = head
    data1 = [1, 2, 7, 9, 14, 15, 
             23, 24, 8, 16, 17]
    data2 = [18, 19, 20, 21, 10, 
             11, 12, 3, 4]
    while (curr == None):
        print(curr.data, "", end = "")
        curr = curr.Next
    for data in data1:
        print(data, "", end = "")
    for data in data2:
        print(data, "", end = "")
  
# Utility function to create a 
# new node
def push(newData):
    newNode = Node(newData)
    return newNode
  
head = Node(1)
head.Next = Node(2)
head.Next.Next = Node(3)
head.Next.Next.Next = Node(4)
head.Next.down = Node(7)
head.Next.down.down = Node(9)
head.Next.down.down.down = 
Node(14)
head.Next.down.down.down.down = 
Node(15)
head.Next.down.down.down.down.Next = 
Node(23)
head.Next.down.down.down.down.Next.down = 
Node(24)
head.Next.down.Next = Node(8)
head.Next.down.Next.down = Node(16)
head.Next.down.Next.down.down = 
Node(17)
head.Next.down.Next.down.down.Next = 
Node(18)
head.Next.down.Next.down.down.Next.Next = 
Node(19)
head.Next.down.Next.down.down.Next.Next.Next = 
Node(20)
head.Next.down.Next.down.down.Next.Next.Next.down = 
Node(21)
head.Next.down.Next.Next = Node(10)
head.Next.down.Next.Next.down = Node(11)
head.Next.down.Next.Next.Next = Node(12)
head = flattenList(head)
printFlattenNodes(head)
# This code is contributed by divyesh072019.

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

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

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