Programa Java para fusionar dos listas enlazadas ordenadas en una nueva lista

Tenemos dos listas ordenadas y nuestro objetivo es fusionar estas dos listas en una nueva lista. Para eso, tenemos que escribir una función que tomará dos List como un argumento que se ordena en orden creciente. Esta función fusionará estas dos listas en una lista en orden creciente. 

Input
List 1 : 1-> 3-> 4-> 9->10
List 2 : 2-> 5-> 6-> 9

Output
New List : 1-> 2-> 3-> 4-> 5-> 6-> 9-> 9-> 10

Tenemos dos enfoques para resolver este problema:

1. Iterativo
2. recursivo

Método 1: enfoque iterativo

• La idea detrás de este enfoque es que tomaremos un Node adicional en la nueva lista, que es el Node principal de la lista.
• Tomaremos una variable del tipo lista que siempre está en el último Node de la lista para que sea más fácil agregar un nuevo Node.
• Repetiremos el ciclo y buscaremos el elemento más pequeño de ambas listas y agregaremos ese Node a la lista resultante.
• Si llegamos al final de cualquier lista, simplemente agregaremos los Nodes restantes de la segunda lista.

Implementación:

// Java Program to Merge Two Sorted
// Linked Lists in New List
// Iteratively
 
import java.io.*;
 
public class ListNode {
 
    int val;
    ListNode next;
 
    ListNode() {}
    ListNode(int val) { this.val = val; }
 
    ListNode(int val, ListNode next)
    {
        this.val = val;
        this.next = next;
    }
}
 
class GFG {
    public static ListNode mergeTwoLists(ListNode l1,
                                         ListNode l2)
    {
        // New List
        ListNode result = new ListNode(-1);
 
        // variable to point the last node of the list.
        ListNode p = result;
 
        // Iterate the loop
        while (l1 != null && l2 != null) {
            // Find the smaller element and append it to the
            // list.
            if (l1.val <= l2.val) {
                p.next = l1;
                l1 = l1.next;
            }
 
            else {
                p.next = l2;
                l2 = l2.next;
            }
 
            // Update the variable
            p = p.next;
        }
 
        // If anyone list become empty append the remaining
        // list element of othe list.
        if (l1 == null) {
            p.next = l2;
        }
 
        else if (l2 == null) {
            p.next = l1;
        }
 
        // Return the resultant list without first extra
        // node
        return result.next;
    }
 
    // A utility function to print linked list
    static void printList(ListNode node)
    {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(3);
        head1.next.next = new ListNode(5);
 
        // 1->3->5 LinkedList created
        ListNode head2 = new ListNode(0);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(4);
 
        // 0->2->4 LinkedList created
        ListNode mergedhead = mergeTwoLists(head1, head2);
 
        printList(mergedhead);
    }
}

0 1 2 3 4 5 

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)

Método 2: enfoque recursivo

Uno puede resolver este problema utilizando el enfoque de recursividad. 

• La función tomará dos listas ordenadas como argumento.
• Si alguna lista está vacía, simplemente devuelve los elementos restantes de la otra lista.
• De lo contrario, buscará el elemento más pequeño de ambas listas, agregará el Node más pequeño a la lista resultante y llamará recursivamente a la función para el siguiente Node de la lista y otra lista.

Implementación:

// Java Program to Merge Two Sorted
// Linked Lists in New List
// Recursively
 
import java.io.*;
 
public class ListNode {
 
    int val;
    ListNode next;
 
    ListNode() {}
    ListNode(int val) { this.val = val; }
 
    ListNode(int val, ListNode next)
    {
        this.val = val;
        this.next = next;
    }
}
 
class GFG {
 
    public static ListNode mergeTwoLists(ListNode l1,
                                         ListNode l2)
    {
 
        // New List
        ListNode result = null;
 
        // If anyone list is empty then returns the
        // remaining elements of other list
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
 
        // Find the smaller element and recusivly call the
        // function with next node
        if (l1.val <= l2.val) {
            result = l1;
            result.next = mergeTwoLists(l1.next, l2);
        }
        else {
            result = l2;
            result.next = mergeTwoLists(l1, l2.next);
        }
 
        // Return the resultant list
        return (result);
    }
    // A utility function to print linked list
    static void printList(ListNode node)
    {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        ListNode head1 = new ListNode(23);
        head1.next = new ListNode(35);
        head1.next.next = new ListNode(65);
 
        // 23->35->65 LinkedList created
        ListNode head2 = new ListNode(43);
        head2.next = new ListNode(59);
        head2.next.next = new ListNode(60);
 
        // 43->59->60 LinkedList created
        ListNode mergedhead = mergeTwoLists(head1, head2);
 
        printList(mergedhead);
    }
}

23 35 43 59 60 65 

Complejidad de tiempo: O(N)

Espacio auxiliar: O (N) para la pila de llamadas desde que se usa la recursividad