Programa de Python para aplanar una lista enlazada

Dada una lista enlazada donde cada Node representa una lista enlazada y contiene dos punteros de su tipo:

Puntero al siguiente Node en la lista principal (lo llamamos puntero ‘derecho’ en el código a continuación).
Puntero a una lista vinculada a la que se dirige este Node (lo llamamos el puntero ‘abajo’ en el código a continuación).

Todas las listas enlazadas están ordenadas. Ver el siguiente ejemplo

       5 -> 10 -> 19 -> 28
       |    |     |     |
       V    V     V     V
       7    20    22    35
       |          |     |
       V          V     V
       8          50    40
       |                |
       V                V
       30               45

Escriba una función flatten() para aplanar las listas en una sola lista enlazada. La lista enlazada aplanada también debe ordenarse. Por ejemplo, para la lista de entrada anterior, la lista de salida debe ser 5->7->8->10->19->20->22->28->30->35->40->45->50 .

La idea es usar el proceso Merge() de clasificación por fusión para listas enlazadas. Usamos merge() para fusionar listas una por una. Fusionamos recursivamente() la lista actual con la lista ya aplanada.
El puntero hacia abajo se usa para vincular Nodes de la lista plana.

A continuación se muestra la implementación del enfoque anterior:

Python3

# Python program for flattening
# a Linked List
class Node():
    def __init__(self, data):
        self.data = data
        self.right = None
        self.down = None
 
class LinkedList():
    def __init__(self):
 
        # Head of list
        self.head = None
 
    # Utility function to insert a
    # node at beginning of the
    # linked list
    def push(self, head_ref, data):
 
        # 1 & 2: Allocate the Node &
        # Put in the data
        new_node = Node(data)
 
        # Make next of new Node as head
        new_node.down = head_ref
 
        # 4. Move the head to point to
        # new Node
        head_ref = new_node
 
        # 5. Return to link it back
        return head_ref
 
    def printList(self):
        temp = self.head
 
        while(temp != None):
            print(temp.data, end = " ")
            temp = temp.down
 
        print()
 
    # An utility function to merge two
    # sorted linked lists
    def merge(self, a, b):
 
        # If the first linked list is empty
        # then second is the answer
        if(a == None):
            return b
         
        # If second linked list is empty
        # then first is the result
        if(b == None):
            return a
 
        # Compare the data members of the
        # two linked lists and put the
        # larger one in the result
        result = None
 
        if (a.data < b.data):
            result = a
            result.down =
            self.merge(a.down,b)
        else:
            result = b
            result.down =
            self.merge(a,b.down)
 
        result.right = None
        return result
 
    def flatten(self, root):
 
        # Base Case
        if(root == None or
           root.right == None):
            return root
 
        # Recur for list on right
        root.right =
        self.flatten(root.right)
 
        # Now merge
        root =
        self.merge(root, root.right)
 
        # Return the root
        # It will be in turn merged with
        # its left
        return root
 
# Driver code
L = LinkedList()
 
'''
Let us create the following linked list
            5 -> 10 -> 19 -> 28
            |    |     |     |
            V    V     V     V
            7    20    22    35
            |          |     |
            V          V     V
            8          50    40
            |                |
            V                V
            30               45
'''
L.head = L.push(L.head, 30);
L.head = L.push(L.head, 8);
L.head = L.push(L.head, 7);
L.head = L.push(L.head, 5);
 
L.head.right =
L.push(L.head.right, 20);
L.head.right =
L.push(L.head.right, 10);
 
L.head.right.right =
L.push(L.head.right.right, 50);
L.head.right.right =
L.push(L.head.right.right, 22);
L.head.right.right =
L.push(L.head.right.right, 19);
 
L.head.right.right.right =
L.push(L.head.right.right.right, 45);
L.head.right.right.right =
L.push(L.head.right.right.right, 40);
L.head.right.right.right =
L.push(L.head.right.right.right, 35);
L.head.right.right.right =
L.push(L.head.right.right.right, 20);
 
# Flatten the list
L.head = L.flatten(L.head);
 
L.printList()
# This code is contributed by maheshwaripiyush9

Producción:

5 7 8 10 19 20 20 22 30 35 40 45 50

Complejidad de tiempo: O(N*N*M) – donde N es el número de Nodes en la lista enlazada principal (accesible usando el puntero derecho) y M es el número de Node en una sola lista subvinculada (accesible usando el puntero hacia abajo).
Complejidad espacial: O(N*M) ya que las funciones recursivas utilizarán una pila recursiva de tamaño equivalente al número total de elementos en las listas.

Consulte el artículo completo sobre Aplanar una lista vinculada para obtener más detalles.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Python3

Deja una respuesta Cancelar la respuesta