Cómo fusionar dos listas ordenadas

Descripción de la tarea:

Se le dan los encabezados de dos listas enlazadas ordenadas list1 y list2 .

Combine las dos listas en una lista ordenada . La lista debe hacerse empalmando los nodos de las dos primeras listas.

Devuelve el encabezado de la lista enlazada fusionada .

Ejemplo 1:

 Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

Ejemplo 2:

 Input: list1 = [], list2 = [] Output: []

Ejemplo 3:

 Input: list1 = [], list2 = [0] Output: [0]

Restricciones:

• El número de nodos en ambas listas está en el rango [0, 50] .
• -100 <= Node.val <= 100
• Tanto list1 como list2 se ordenan en orden no decreciente .

Razonamiento:

LinkedList es otra estructura de datos ampliamente utilizada. Puede ser de enlace simple o enlace doble.

Para esta tarea en particular, podemos suponer que trabajamos con una versión de enlace único. Como puede ver, cada lista enlazada consta de pequeñas piezas llamadas Enlaces o Nodo.

https://gist.github.com/RakhmedovRS/341071fbc066bcf4a3b2c228e51fc7ff

Como puede ver en las imágenes y el código de arriba, cada LinkedNode almacena un enlace al siguiente LinkedNode. El primer LinkedNode generalmente se llama cabeza, mientras que el último se llama cola. Con una versión de enlace único, solo podemos atravesar de la cabeza a la cola de la lista y no hay forma de volver al nodo anterior una vez que avanzamos. La versión doblemente enlazada nos permite atravesar en ambas direcciones porque cada ListNode almacena punteros a los ListNodes siguientes y anteriores.

Solución:

Esta vez proporciono el código completo para la solución y lo discutiremos.

https://gist.github.com/RakhmedovRS/9d7bff26fae314a46d13420028842992

Lo primero que hacemos es crear un nodo ficticio para almacenar enlaces al futuro encabezado de la lista enlazada fusionada, como dije anteriormente, cada LinkedList tiene un encabezado.

También necesitamos un nodo actual para almacenar el enlace del nodo actual, por lo que podemos usarlo para adjuntarle el siguiente nodo.

Iteramos a través de ambas listas hasta que los punteros a los siguientes nodos no sean nulos. En cada uno de esos pasos, estamos buscando un nodo con un valor mínimo almacenado en él. Movemos el puntero al siguiente para LinkedList que tiene un nodo actual con un valor mínimo. Eventualmente, uno de los punteros de ambos es nulo.

Lo último que debemos hacer es adjuntar el resto de LinkedList que todavía tiene algunos valores a nuestro puntero actual y devolver un encabezado de la LinkedList recién creada.

La solución anterior tiene una complejidad de tiempo lineal y no utiliza memoria adicional (en términos de notación O grande, se pueden omitir punteros adicionales)

Nos vemos en el próximo artículo✌️✌️✌️✌️✌️✌️✌️