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.
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
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