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.
C++
// C program to merge two sorted
// linked lists in-place.
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* next;
};
// Function to create newNode
// in a linkedlist
Node* newNode(int key)
{
struct Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// A utility function to print
// linked list
void printList(Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
// Merges two given lists in-place.
// This function mainly compares head
// nodes and calls mergeUtil()
Node* merge(Node* h1, Node* h2)
{
if (!h1)
return h2;
if (!h2)
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
int main()
{
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);
return 0;
}
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.
C++
// C++ program to merge two sorted
// linked lists in-place.
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* next;
};
// Function to create newNode in
// a linkedlist
struct Node* newNode(int key)
{
struct Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// A utility function to print
// linked list
void printList(struct Node* node)
{
while (node != NULL)
{
printf("%d ", 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.
struct Node* mergeUtil(struct Node* h1,
struct Node* h2)
{
// If only one node in first list
// simply point its head to second list
if (!h1->next)
{
h1->next = h2;
return h1;
}
// Initialize current and next pointers
// of both lists
struct Node *curr1 = h1,
*next1 = h1->next;
struct Node *curr2 = h2,
*next2 = h2->next;
while (next1 && curr2)
{
// 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)
{
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()
struct Node* merge(struct Node* h1,
struct Node* h2)
{
if (!h1)
return h2;
if (!h2)
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
int main()
{
struct Node* head1 = newNode(1);
head1->next = newNode(3);
head1->next->next = newNode(5);
// 1->3->5 LinkedList created
struct Node* head2 = newNode(0);
head2->next = newNode(2);
head2->next->next = newNode(4);
// 0->2->4 LinkedList created
struct Node* mergedhead = merge(head1, head2);
printList(mergedhead);
return 0;
}
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