Dadas dos listas enlazadas ordenadas en orden creciente. Combínalos de tal manera que la lista de resultados esté en orden decreciente (orden inverso).
Ejemplos:
Input: a: 5->10->15->40
b: 2->3->20
Output: res: 40->20->15->10->5->3->2
Input: a: NULL
b: 2->3->20
Output: res: 20->3->2
Una solución simple es hacer lo siguiente.
1) Invertir la primera lista ‘a’ .
2) Invertir la segunda lista ‘b’ .
3) Combinar dos listas invertidas .
Otra solución simple es primero fusionar ambas listas, luego invertir la lista fusionada.
Ambas soluciones anteriores requieren dos recorridos de lista enlazada.
¿Cómo resolver sin reversa, O(1) espacio auxiliar (en el lugar) y solo un recorrido de ambas listas?
La idea es seguir el proceso de estilo de fusión. Inicializa la lista de resultados como vacía. Recorra ambas listas de principio a fin. Compare los Nodes actuales de ambas listas e inserte el menor de dos al principio de la lista de resultados.
1) Initialize result list as empty: res = NULL.
2) Let 'a' and 'b' be heads first and second lists respectively.
3) While (a != NULL and b != NULL)
a) Find the smaller of two (Current 'a' and 'b')
b) Insert the smaller value node at the front of the result.
c) Move ahead in the list of the smaller nodes.
4) If 'b' becomes NULL before 'a', insert all nodes of 'a'
into the result list at the beginning.
5) If 'a' becomes NULL before 'b', insert all nodes of 'a'
into result list at the beginning.
A continuación se muestra la implementación de la solución anterior.
C++14
// C++ program to implement
// the above approach
#include<iostream>
using namespace std;
// Link list Node
struct Node
{
int key;
struct Node* next;
};
// Given two non-empty linked lists
// 'a' and 'b'
Node* SortedMerge(Node *a, Node *b)
{
// If both lists are empty
if (a==NULL && b==NULL)
return NULL;
// Initialize head of resultant
// list
Node *res = NULL;
// Traverse both lists while both
// of then have nodes.
while (a != NULL && b != NULL)
{
// If a's current value is smaller
// or equal to b's current value.
if (a->key <= b->key)
{
// Store next of current Node
// in first list
Node *temp = a->next;
// Add 'a' at the front of
// resultant list
a->next = res;
res = a;
// Move ahead in first list
a = temp;
}
// If a's value is greater. Below steps
// are similar to above (Only 'a' is
// replaced with 'b')
else
{
Node *temp = b->next;
b->next = res;
res = b;
b = temp;
}
}
// If second list reached end, but first
// list has nodes. Add remaining nodes of
// first list at the front of result list
while (a != NULL)
{
Node *temp = a->next;
a->next = res;
res = a;
a = temp;
}
// If first list reached end, but second
// list has node. Add remaining nodes of
// first list at the front of result list
while (b != NULL)
{
Node *temp = b->next;
b->next = res;
res = b;
b = temp;
}
return res;
}
/* Function to print Nodes in a
given linked list */
void printList(struct Node *Node)
{
while (Node!=NULL)
{
cout << Node->key << " ";
Node = Node->next;
}
}
/* Utility function to create a
new node with given key */
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// Driver code
int main()
{
// Start with the empty list
struct Node* res = NULL;
/* Let us create two sorted linked
lists to test the above functions.
Created lists shall be
a: 5->10->15
b: 2->3->20 */
Node *a = newNode(5);
a->next = newNode(10);
a->next->next = newNode(15);
Node *b = newNode(2);
b->next = newNode(3);
b->next->next = newNode(20);
cout << "List A before merge: ";
printList(a);
cout << "List B before merge: ";
printList(b);
/* Merge 2 increasing order LLs
in descresing order */
res = SortedMerge(a, b);
cout << "Merged Linked List is: ";
printList(res);
return 0;
}
Producción:
List A before merge: 5 10 15 List B before merge: 2 3 20 Merged Linked List is: 20 15 10 5 3 2
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Esta solución atraviesa ambas listas solo una vez, no requiere inversión y funciona en el lugar.
Este artículo es una contribución de Mohammed Raqeeb . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
¡ Consulte el artículo completo sobre Fusionar dos listas enlazadas ordenadas de modo que la lista fusionada esté en orden inverso 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