Programa de Python para fusionar K listas enlazadas ordenadas – Conjunto 1

Dadas K listas enlazadas ordenadas de tamaño N cada una, combínelas e imprima la salida ordenada.

Ejemplos: 

Input: k = 3, n =  4
list1 = 1->3->5->7->NULL
list2 = 2->4->6->8->NULL
list3 = 0->9->10->11->NULL

Output: 0->1->2->3->4->5->6->7->8->9->10->11
Merged lists in a sorted order 
where every element is greater 
than the previous element.

Input: k = 3, n =  3
list1 = 1->3->7->NULL
list2 = 2->4->8->NULL
list3 = 9->10->11->NULL

Output: 1->2->3->4->7->8->9->10->11
Merged lists in a sorted order 
where every element is greater 
than the previous element.

Método 1 (Simple):

Enfoque: 
una solución simple es inicializar el resultado como la primera lista. Ahora recorra todas las listas a partir de la segunda lista. Inserte cada Node de la lista recorrida actualmente en el resultado de forma ordenada.

# Python3 program to merge k 
# sorted arrays of size n each
  
# A Linked List node
class Node:  
    def __init__(self, x):      
        self.data = x
        self.next = None
  
# Function to print nodes in a given 
# linked list 
def printList(node):
    
    while (node != None):
        print(node.data, 
              end = " ")
        node = node.next
  
# The main function that takes an 
# array of lists arr[0..last] and 
# generates the sorted output
def mergeKLists(arr, last):
  
    # Traverse form second 
    # list to last
    for i in range(1, last + 1):
        while (True):
            # head of both the lists,
            # 0 and ith list.
            head_0 = arr[0]
            head_i = arr[i]
  
            # Break if list ended
            if (head_i == None):
                break
  
            # Smaller than first 
            # element
            if (head_0.data >= 
                head_i.data):
                arr[i] = head_i.next
                head_i.next = head_0
                arr[0] = head_i
            else:
                # Traverse the first list
                while (head_0.next != None):
                    # Smaller than next 
                    # element
                    if (head_0.next.data >= 
                        head_i.data):
                        arr[i] = head_i.next
                        head_i.next = head_0.next
                        head_0.next = head_i
                        break
                    # go to next node
                    head_0 = head_0.next
                    # if last node
                    if (head_0.next == None):
                        arr[i] = head_i.next
                        head_i.next = None
                        head_0.next = head_i
                        head_0.next.next = None
                        break
    return arr[0]
  
# Driver code
if __name__ == '__main__':
    
    # Number of linked 
    # lists
    k = 3
      
    # Number of elements
    # in each list
    n = 4
  
    # an array of pointers 
    # storing the head nodes 
    # of the linked lists
    arr = [None for i in range(k)]
  
    arr[0] = Node(1)
    arr[0].next = Node(3)
    arr[0].next.next = Node(5)
    arr[0].next.next.next = Node(7)
  
    arr[1] = Node(2)
    arr[1].next = Node(4)
    arr[1].next.next = Node(6)
    arr[1].next.next.next = Node(8)
  
    arr[2] = Node(0)
    arr[2].next = Node(9)
    arr[2].next.next = Node(10)
    arr[2].next.next.next = Node(11)
  
    # Merge all lists
    head = mergeKLists(arr, k - 1)
  
    printList(head)
# This code is contributed by Mohit Kumar 29

Producción:

0 1 2 3 4 5 6 7 8 9 10 11

Análisis de Complejidad: 

• Complejidad del tiempo: O(nk ² )
• Espacio Auxiliar: O(1). 
  Como no se requiere espacio adicional.

Método 2: montón mínimo . 
Una mejor solución es usar una solución basada en Min Heap que se analiza aquí para arreglos. La complejidad temporal de esta solución sería O(nk Log k)
Método 3: divide y vencerás . 
En esta publicación, se analiza el enfoque Divide and Conquer . Este enfoque no requiere espacio adicional para el almacenamiento dinámico y funciona en O(nk Log k).
Se sabe que la fusión de dos listas enlazadas se puede realizar en tiempo O(n) y espacio O(n). 

1. La idea es emparejar K listas y fusionar cada par en tiempo lineal usando el espacio O(n).
2. Después del primer ciclo, se dejan listas K/2 cada una de tamaño 2*N. Después del segundo ciclo, se dejan listas K/4 cada una de tamaño 4*N y así sucesivamente.
3. Repita el procedimiento hasta que solo nos quede una lista.

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

# Python3 program to merge k sorted
# arrays of size n each
   
# A Linked List node
class Node:    
    def __init__(self):
          
        self.data = 0
        self.next = None
  
# Function to print nodes in a
# given linked list
def printList(node):
    while (node != None):
        print(node.data, end = ' ')
        node = node.next
      
# Takes two lists sorted in increasing order, 
# and merge their nodes together to make one 
# big sorted list. Below function takes 
# O(Log n) extra space for recursive calls,
# but it can be easily modified to work with
# same time and O(1) extra space 
def SortedMerge(a, b):
    result = None
   
    # Base cases 
    if (a == None):
        return(b)
    elif (b == None):
        return(a)
   
    # Pick either a or b, and recur 
    if (a.data <= b.data):
        result = a
        result.next = 
               SortedMerge(a.next, b)
    else:
        result = b
        result.next = 
               SortedMerge(a, b.next)
      
    return result
  
# The main function that takes an array 
# of lists arr[0..last] and generates 
# the sorted output
def mergeKLists(arr, last):
  
    # Repeat until only one list is left
    while (last != 0):
        i = 0
        j = last
   
        # (i, j) forms a pair
        while (i < j):
              
            # Merge List i with List j and store
            # merged list in List i
            arr[i] = SortedMerge(arr[i], arr[j])
   
            # Consider next pair
            i += 1
            j -= 1
              
            # If all pairs are merged, update last
            if (i >= j):
                last = j
   
    return arr[0]
  
# Utility function to create a new node.
def newNode(data):
  
    temp = Node()
    temp.data = data
    temp.next = None
    return temp
  
# Driver code
if __name__=='__main__':
      
    # Number of linked lists
    k = 3
      
    # Number of elements in each list
    n = 4 
   
    # An array of pointers storing the 
    # head nodes of the linked lists
    arr = [0 for i in range(k)]
   
    arr[0] = newNode(1)
    arr[0].next = newNode(3)
    arr[0].next.next = newNode(5)
    arr[0].next.next.next = newNode(7)
   
    arr[1] = newNode(2)
    arr[1].next = newNode(4)
    arr[1].next.next = newNode(6)
    arr[1].next.next.next = newNode(8)
   
    arr[2] = newNode(0)
    arr[2].next = newNode(9)
    arr[2].next.next = newNode(10)
    arr[2].next.next.next = newNode(11)
   
    # Merge all lists
    head = mergeKLists(arr, k - 1)
   
    printList(head)
  
# This code is contributed by rutvik_56

Producción:

0 1 2 3 4 5 6 7 8 9 10 11

Análisis de Complejidad: 

Suponiendo que N(n*k) es el número total de Nodes, n es el tamaño de cada lista vinculada y k es el número total de listas vinculadas.

• Complejidad de tiempo: O(N*log k) u O(n*k*log k)
  Como ciclo while externo en la función mergeKLists() ejecuta log k veces y cada vez que procesa n*k elementos.
• Espacio auxiliar: O(N) u O(n*k)
  Debido a que la recursividad se usa en SortedMerge() y para fusionar las 2 listas enlazadas finales de tamaño N/2, se realizarán N llamadas recursivas.

Consulte el artículo completo sobre las listas enlazadas ordenadas de Merge K | ¡ Establezca 1 para más detalles!