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.
- Compare el encabezado de ambas listas enlazadas.
- 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.
- El resto de elementos de ambas listas aparecerán después de eso.
- Ahora ejecute una función recursiva con parámetros, el siguiente Node del elemento más pequeño y la otra cabeza.
- 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()
- Manejar algunos casos de esquina.
- Si ambas cabezas son NULL, devuelve nulo.
- Si una cabeza es nula, devuelve la otra.
Java
// Java program to merge two sorted
// linked lists in-place.
class GFG
{
static class Node
{
int data;
Node next;
};
// Function to create newNode in
// a linkedlist
static Node newNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// A utility function to print
// linked list
static void printList(Node node)
{
while (node != null)
{
System.out.printf("%d ",
node.data);
node = node.next;
}
}
// Merges two given lists in-place.
// This function mainly compares head
// nodes and calls mergeUtil()
static Node merge(Node h1, Node 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 program
public static void main(String args[])
{
Node head1 = newNode(1);
head1.next = newNode(3);
head1.next.next = newNode(5);
// 1.3.5 LinkedList created
Node head2 = newNode(0);
head2.next = newNode(2);
head2.next.next = newNode(4);
// 0.2.4 LinkedList created
Node 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).
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.
- Recorra la lista de principio a fin.
- 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.
- 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.
Java
// Java program to merge two sorted
// linked lists in-place.
class GfG
{
static class Node
{
int data;
Node next;
}
// Function to create newNode in
// a linkedlist
static Node newNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// A utility function to print
// linked list
static void printList(Node node)
{
while (node != null)
{
System.out.print(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.
static Node mergeUtil(Node h1, Node 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
Node curr1 = h1, next1 = h1.next;
Node 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()
static Node merge(Node h1, Node 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
public static void main(String[] args)
{
Node head1 = newNode(1);
head1.next = newNode(3);
head1.next.next = newNode(5);
// 1->3->5 LinkedList created
Node head2 = newNode(0);
head2.next = newNode(2);
head2.next.next = newNode(4);
// 0->2->4 LinkedList created
Node mergedhead = merge(head1,
head2);
printList(mergedhead);
}
}
// This code is contributed by prerna saini
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.
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