Programa de Python para fusionar dos listas ordenadas (in situ)

Dadas dos listas ordenadas, combínelas para producir una lista ordenada combinada (sin usar espacio adicional).
Ejemplos:

Input: head1: 5->7->9
        head2: 4->6->8 
Output: 4->5->6->7->8->9
Explanation: The output list is in sorted order.

Input: head1: 1->3->5->7
        head2: 2->4
Output: 1->2->3->4->5->7
Explanation: The output list is in sorted order.

Hay diferentes soluciones discutidas en la publicación a continuación. 
Combinar dos listas enlazadas ordenadas

Método 1 (recursivo):

Enfoque: la solución recursiva se puede formar, dado que las listas enlazadas están ordenadas.

1. Compare el encabezado de ambas listas enlazadas.
2. Encuentra el Node más pequeño entre los dos Nodes principales. El elemento actual será el Node más pequeño entre dos Nodes principales.
3. El resto de elementos de ambas listas aparecerán después de eso.
4. Ahora ejecute una función recursiva con parámetros, el siguiente Node del elemento más pequeño y la otra cabeza.
5. La función recursiva devolverá el siguiente elemento más pequeño vinculado con el resto del elemento ordenado. Ahora apunte el siguiente elemento actual a eso, es decir, curr_ele->next=recursivefunction()
6. Manejar algunos casos de esquina. 
   • Si ambas cabezas son NULL, devuelve nulo.
   • Si una cabeza es nula, devuelve la otra.

# Python3 program to merge two 
# sorted linked lists in-place.
import math
class Node: 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
# Function to create newNode in 
# a linkedlist
def newNode(key):
    temp = Node(key)
    temp.data = key
    temp.next = None
    return temp
  
# A utility function to print 
# linked list
def printList(node):
    while (node != None):
        print(node.data, 
              end = " ")
        node = node.next
  
# Merges two given lists in-place. 
# This function mainly compares 
# head nodes and calls mergeUtil()
def merge(h1, h2):
    if (h1 == None):
        return h2
    if (h2 == None):
        return h1
  
    # start with the linked list
    # whose head data is the least
    if (h1.data < h2.data):
        h1.next = merge(h1.next, h2)
        return h1
      
    else:
        h2.next = merge(h1, h2.next)
        return h2
      
# Driver Code
if __name__=='__main__': 
    head1 = newNode(1)
    head1.next = newNode(3)
    head1.next.next = newNode(5)
  
    # 1.3.5 LinkedList created
    head2 = newNode(0)
    head2.next = newNode(2)
    head2.next.next = newNode(4)
  
    # 0.2.4 LinkedList created
    mergedhead = merge(head1, head2)
  
    printList(mergedhead)
  
# This code is contributed by Srathore

Producción:  

0 1 2 3 4 5 

Análisis de Complejidad:

• Complejidad temporal: O(n). 
  Solo se necesita un recorrido de las listas enlazadas.
• Espacio Auxiliar: O(n). 
  Si se tiene en cuenta el espacio de pila recursivo.

Método 2 (iterativo):

Enfoque: Este enfoque es muy similar al enfoque recursivo anterior.

1. Recorra la lista de principio a fin.
2. Si el Node principal de la segunda lista se encuentra entre dos Nodes de la primera lista, insértelo allí y haga que el siguiente Node de la segunda lista sea el encabezado. Continúe hasta que no quede ningún Node en ambas listas, es decir, se recorren ambas listas.
3. Si la primera lista ha llegado al final durante el recorrido, apunte el siguiente Node al encabezado de la segunda lista.

Nota: Compare ambas listas donde la lista con un valor de cabeza más pequeño es la primera lista.

# Python program to merge two 
# sorted linked lists in-place.
# Linked List node 
class Node: 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
# Function to create newNode in 
# a linkedlist
def newNode(key):
    temp = Node(0)
    temp.data = key
    temp.next = None
    return temp
  
# A utility function to print 
# linked list
def printList(node):
  
    while (node != None) :
        print( node.data, end =" ")
        node = node.next
      
# Merges two lists with headers as h1 and h2.
# It assumes that h1's data is smaller than
# or equal to h2's data.
def mergeUtil(h1, h2):
  
    # if only one node in first list
    # simply point its head to second 
    # list
    if (h1.next == None) :
        h1.next = h2
        return h1
      
    # Initialize current and next 
    # pointers of both lists
    curr1 = h1
    next1 = h1.next
    curr2 = h2
    next2 = h2.next
  
    while (next1 != None and 
           curr2 != None): 
      
        # if curr2 lies in between curr1 
        # and next1 then do curr1.curr2.next1
        if ((curr2.data) >= (curr1.data) and
            (curr2.data) <= (next1.data)):
            next2 = curr2.next
            curr1.next = curr2
            curr2.next = next1
  
            # now let curr1 and curr2 to point
            # to their immediate next pointers
            curr1 = curr2
            curr2 = next2
          
        else:
            # if more nodes in first list
            if (next1.next) :
                next1 = next1.next
                curr1 = curr1.next
              
            # else point the last node of first list
            # to the remaining nodes of second list
            else:
                next1.next = curr2
                return h1
  
    return h1
  
# Merges two given lists in-place. 
# This function mainly compares head 
# nodes and calls mergeUtil()
def merge(h1, h2):
  
    if (h1 == None):
        return h2
    if (h2 == None):
        return h1
  
    # Start with the linked list
    # whose head data is the least
    if (h1.data < h2.data):
        return mergeUtil(h1, h2)
    else:
        return mergeUtil(h2, h1)
  
# Driver code
head1 = newNode(1)
head1.next = newNode(3)
head1.next.next = newNode(5)
  
# 1.3.5 LinkedList created
head2 = newNode(0)
head2.next = newNode(2)
head2.next.next = newNode(4)
  
# 0.2.4 LinkedList created
mergedhead = merge(head1, head2)
  
printList(mergedhead)
# This code is contributed by Arnab Kundu

Producción:  

0 1 2 3 4 5 

Análisis de Complejidad:

• Complejidad temporal: O(n). 
  Como solo se necesita un recorrido de las listas enlazadas.
• Espacio Auxiliar: O(1). 
  Como no se requiere espacio.

Consulte el artículo completo sobre Fusionar dos listas ordenadas (in situ) para obtener más detalles.