Cómo fusionar dos listas ordenadas by@rakhmedovrs
94,418 lecturas

Cómo fusionar dos listas ordenadas

2022/08/01
2 min
por @rakhmedovrs 94,418 lecturas
tldt arrow
ES
Read on Terminal Reader

Demasiado Largo; Para Leer

La lista debe hacerse empalmando los nodos de las dos primeras listas. Puede ser de enlace simple o enlace doble. El número de nodos en ambas listas está en el rango `[0, 50]`-100 <= 100` El primer nodo vinculado generalmente se llama cabeza, mientras que el último se llama cola. La solución tiene una solución y la discutiremos en términos de notación O grande. Estamos buscando un nodo con un valor mínimo almacenado en él. Pasamos el puntero al siguiente de LinkedList que tiene cabeza. También necesitamos un nodo actual para almacenar el enlace del nodo actual.
featured image - Cómo fusionar dos listas ordenadas
Ruslan Rakhmedov HackerNoon profile picture

@rakhmedovrs

Ruslan Rakhmedov

Senior Software Engineer. As a hobby I do competitive programming...

Aprender Mas
LEARN MORE ABOUT @RAKHMEDOVRS'S EXPERTISE AND PLACE ON THE INTERNET.
react to story with heart

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:

image

 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.

Lista enlazada simple

Lista enlazada simple

Lista doblemente enlazada

Lista doblemente enlazada

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.

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.

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)

image

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

HISTORIAS RELACIONADAS

L O A D I N G
. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa