Dadas dos listas ordenadas enlazadas individualmente que tienen n y m elementos cada una, combínelas usando un espacio constante. Los primeros n elementos más pequeños en ambas listas deben formar parte de la primera lista y los demás 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.
Por 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 la 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 vuelve un poco complicado 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 de enlaces únicos, 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 discrepancias atravesando 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;
}
Python3
# Python3 program to merge two sorted linked
# lists without using any extra space and
# without changing links of first list
# Structure for a linked list node
class Node:
def __init__(self):
self.data = 0
self.next = None
# 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.
def push(head_ref, new_data):
# Allocate node
new_node = 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
return head_ref
# Function to merge two sorted linked lists
# LL1 and LL2 without using any extra space.
def mergeLists(a, b):
# Run till either one of a
# or b runs out
while (a and 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
a.data, b.data = b.data, a.data
temp = b
# To keep LL2 sorted, place first
# element of LL2 at its correct place
if (b.next and b.data > b.next.data):
b = b.next
ptr = b
prev = None
# Find mismatch by traversing the
# second linked list once
while (ptr and 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
# Function to print the linked link
def printList(head):
while (head):
print(head.data, end = '->')
head = head.next
print('NULL')
# Driver code
if __name__=='__main__':
a = None
a = push(a, 10)
a = push(a, 8)
a = push(a, 7)
a = push(a, 4)
a = push(a, 2)
b = None
b = push(b, 12)
b = push(b, 3)
b = push(b, 1)
mergeLists(a, b)
print("First List: ", end = '')
printList(a)
print("Second List: ", end = '')
printList(b)
# This code is contributed by rutvik_56
First List: 1->2->3->4->7->NULL Second List: 8->10->12->NULL
Complejidad temporal: O(mn)
Espacio auxiliar: O(1)
Este artículo es una contribución de Aditya Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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