Programa Javascript 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.

<script>
// Javascript program to merge two
// sorted linked lists in-place.   
class Node
{
    constructor()
    {
        this.data = 0;
        this.next = null;
    }
}
 
// Function to create newNode in
// a linkedlist
function newNode(key)
{
    temp = new Node();
    temp.data = key;
    temp.next = null;
    return temp;
}
 
// A utility function to print
// linked list
function printList(node)
{
    while (node != null)
    {
        document.write(node.data+" ");
        node = node.next;
    }
}
 
// Merges two given lists in-place.
// This function mainly compares head
// nodes and calls mergeUtil()
function merge(h1, h2)
{
    if (h1 == null)
        return h2;
     if (h2 == null)
         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
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 umadevi9616
</script>

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.

<script>
// JavaScript program to merge two sorted
// linked lists in-place.
class Node
{
    constructor()
    {
        this.data = 0;
        this.next = null;
    }
}
 
// Function to create newNode in
// a linkedlist
function newNode(key)
{
    var temp = new Node();
    temp.data = key;
    temp.next = null;
    return temp;
}
 
// A utility function to print
// linked list
function printList(node)
{
    while (node != null)
    {
        document.write(node.data + " ");
        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.
function mergeUtil(h1, h2)
{
    // if only one node in first list
    // simply point its head to second list
    if (h1.next == null)
    {
        h1.next = h2;
        return h1;
    }
 
    // Initialize current and next
    // pointers of both lists
    var curr1 = h1, next1 = h1.next;
    var curr2 = h2, next2 = h2.next;
 
    while (next1 != null &&
           curr2 != null)
    {
        // if curr2 lies in between curr1
        // and next1 then do curr1->curr2->next1
        if ((curr2.data) >= (curr1.data) &&
            (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 != null)
            {
                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()
function merge(h1, h2)
{
    if (h1 == null)
        return h2;
    if (h2 == null)
        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
var head1 = newNode(1);
head1.next = newNode(3);
head1.next.next = newNode(5);
 
// 1->3->5 LinkedList created
var head2 = newNode(0);
head2.next = newNode(2);
head2.next.next = newNode(4);
 
// 0->2->4 LinkedList created
var mergedhead = merge(head1, head2);
 
printList(mergedhead);
// This code is contributed by gauravrajput1
</script>

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.