Muy buenas, me llamo Luis y esta vez les traigo este nuevo artículo.
Entender el problema
Se nos dan dos listas enlazadas individualmente y tenemos que encontrar el punto en el que se fusionan.
[SLL 1] 1--->3--->5
\
9--->12--->17--->None
/
[SLL 2] 7--->8
El diagrama de arriba ilustra que la fusión ocurre en el nodo 9.
Podemos estar seguros de que los parámetros que se nos dan, head1 y head2, que son los encabezados de ambas listas, nunca serán iguales y nunca serán ninguno. También se garantiza que las dos listas se fusionarán en algún momento.
Necesitamos un plan para encontrar y devolver el valor de datos enteros del nodo donde se fusionan las dos listas.
Plan
Para recorrer las listas para encontrar el punto en el que se fusionan, necesitamos establecer dos punteros diferentes. Uno para la primera lista enlazada individualmente, otro para la segunda. Recuerde que se nos dan las cabezas de ambos como parámetros, por lo que estableceremos nuestros punteros para comenzar desde el principio de cada uno.
pointer1 = head1 pointer2 = head2
Para comenzar a recorrer las listas, necesitaremos crear un ciclo while para recorrer las listas mientras las listas no son Ninguna.
while not None:
Si en algún punto, pointer1 y pointer2 son iguales, debemos salir del ciclo while, ya que hemos encontrado el nodo donde se fusionan las dos listas.
if pointer1 == pointer2: break
Sin embargo, si no es igual, avanzaremos utilizando en el código .next.
pointer1 = pointer1.next pointer2 = pointer2.next
Como podemos ver en el diagrama de ejemplo, nuestra primera lista enlazada individualmente, SLL 1, es más corta que SLL 2. Así que supongamos que SLL 1 llega a Ninguno antes de que SLL 2 encuentre el nodo de fusión. En este caso, simplemente comenzaremos de nuevo, estableciendo la misma instrucción if para SLL 2, en caso de que tengamos un caso de prueba en nuestro programa donde el segundo SLL es el más corto.
if pointer1 == None:
pointer1 == head1
if pointer2 == None:
pointer2 == head1
Esta lógica de empezar de nuevo se repetirá en el ciclo while hasta que ambos punteros encuentren el nodo de fusión al mismo tiempo, o en otras palabras, hasta que el puntero1 y el puntero2 sean iguales. Cuando eso suceda, debemos recordar hacer lo que se nos pidió y devolver el valor de datos enteros de ese nodo.
return pointer1.data
Debido a que estos también serán los datos de pointer2, podemos devolver esto en lugar de pointer1. Tiene el mismo valor.
return pointer2.data
Ejecutar
# For our reference: # # SinglyLinkedListNode: # int data # SinglyLinkedListNode next # #def findMergeNode(head1, head2): # Set the pointers pointer1 = head1 pointer2 = head2 while not None: # if we found the merging node, then break out of the loop if pointer1 == pointer2: break #traverse through lists pointer1 = pointer1.next pointer2= pointer2.next # Begin again if one was shorter than the other if pointer1 == None: pointer1 = head1 if pointer2 == None: pointer2 = head2 return pointer1.data
Gracias por llegar al final del artículo.
Añadir comentario