Dadas dos listas ordenadas enlazadas individualmente que tienen n y m elementos cada una, combínelas usando un espacio constante. Primero, los n elementos más pequeños en ambas listas deben formar parte de la primera lista y el resto de los elementos deben formar parte de la segunda lista. Se debe mantener el orden ordenado. No se nos permite cambiar los punteros de la primera lista enlazada.
Ejemplo:
Input: First List: 2->4->7->8->10 Second List: 1->3->12 Output: First List: 1->2->3->4->7 Second List: 8->10->12
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
El problema se vuelve muy simple si se nos permite cambiar los punteros de la primera lista enlazada. Si se nos permite cambiar los enlaces, simplemente podemos hacer algo como una fusión del algoritmo de clasificación por fusión. Asignamos los primeros n elementos más pequeños a la primera lista enlazada donde n es el número de elementos en la primera lista enlazada y el resto a la segunda lista enlazada. Podemos lograr esto en el tiempo O(m + n) y en el espacio O(1), pero esta solución viola el requisito de que no podemos cambiar los enlaces de la primera lista.
El problema se complica un poco ya que no se nos permite cambiar los punteros en la primera lista enlazada. La idea es algo similar a esta publicación, pero como se nos da una lista con un solo enlace, no podemos retroceder con el último elemento de LL2.
La idea es que para cada elemento de LL1 lo comparemos con el primer elemento de LL2. Si LL1 tiene un elemento mayor que el primer elemento de LL2, entonces intercambiamos los dos elementos involucrados. Para mantener ordenado LL2, debemos colocar el primer elemento de LL2 en su posición correcta. Podemos encontrar una discrepancia recorriendo LL2 una vez y corrigiendo los punteros.
A continuación se muestra la implementación de esta idea.
C++
// C++ Program to merge two sorted linked lists
// without using any extra space and without
// changing links of first list
#include <bits/stdc++.h>
using namespace std;
// Structure for a linked list node
struct Node
{
int data;
struct Node *next;
};
/* Given a reference (pointer to pointer)
to the head of a list and an int, push
a new node on the front of the list. */
void push(struct Node** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
// Put in the data
new_node->data = new_data;
/* Link the old list off the
new node */
new_node->next = (*head_ref);
/* Move the head to point to
the new node */
(*head_ref) = new_node;
}
// Function to merge two sorted
// linked lists LL1 and LL2 without
// using any extra space.
void mergeLists(struct Node *a,
struct Node * &b)
{
// Run till either one of a or b
// runs out
while (a && b)
{
// For each element of LL1,
// compare it with first element
// of LL2.
if (a->data > b->data)
{
// Swap the two elements involved
// if LL1 has a greater element
swap(a->data, b->data);
struct Node *temp = b;
// To keep LL2 sorted, place
// first element of LL2 at its
// correct place
if (b->next && b->data >
b->next->data)
{
b = b->next;
struct Node *ptr= b,
*prev = NULL;
// Find mismatch by traversing
// the second linked list once
while (ptr && ptr->data <
temp->data)
{
prev = ptr;
ptr = ptr -> next;
}
// correct the pointers
prev->next = temp;
temp->next = ptr;
}
}
// Move LL1 pointer to next element
a = a->next;
}
}
// Code to print the linked link
void printList(struct Node *head)
{
while (head)
{
cout << head->data << "->" ;
head = head->next;
}
cout << "NULL" << endl;
}
// Driver code
int main()
{
struct Node *a = NULL;
push(&a, 10);
push(&a, 8);
push(&a, 7);
push(&a, 4);
push(&a, 2);
struct Node *b = NULL;
push(&b, 12);
push(&b, 3);
push(&b, 1);
mergeLists(a, b);
cout << "First List: ";
printList(a);
cout << "Second List: ";
printList(b);
return 0;
}
Producción :
First List: 1->2->3->4->7->NULL Second List: 8->10->12->NULL
Complejidad de tiempo : O(mn)
Espacio Auxiliar: O(1)
¡ Consulte el artículo completo sobre la fusión en el lugar de dos listas vinculadas sin cambiar los enlaces de la primera lista 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