Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Contenido del curso

Introducción

1
¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?
00:52 min

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos

41
Toma el Curso Avanzado de Algoritmos: Grafos y Árboles
00:33 min

Tomar examen

Ejercicios recomendados de Lista Enlazada

Sumar dos números

Se dan dos listas enlazadas no vacías que representan dos enteros no negativos. Los dígitos están almacenados en orden inverso, y cada uno de sus nodos contiene un solo dígito. Suma los dos números y devuelve la suma como una lista enlazada.

Puede suponer que los dos números no contienen ningún cero inicial, excepto el propio número 0.

Ejemplo 1:

Entrada: 
l1 = [2,4,3], l2 = [5,6,4]


Salida: [7,0,8]

Explicación: 342 + 465 = 807.

Intercambio de nodos por parejas

Dada una lista enlazada, intercambia cada dos nodos adyacentes y devuelve su cabeza. Debe resolver el problema sin modificar los valores de los nodos de la lista (es decir, sólo se pueden cambiar los propios nodos).

Ejemplo 1:
Entrada: cabeza = [1,2,3,4]
Salida: [2,1,4,3]

Historial de un Navegador

Tienes un navegador de una pestaña donde empiezas en la página de inicio y puedes visitar otra url, retroceder en el historial número de pasos o avanzar en el historial número de pasos.

Implementa la clase BrowserHistory:

BrowserHistory(string homepage): inicializa el objeto con la página de inicio del navegador. void visit(string url): visita la url de la página actual. Borra todo el historial de avance. string back(int steps): mueve los pasos hacia atrás en el historial. Si sólo puede devolver x pasos en el historial y pasos > x, devolverá sólo x pasos. Devuelve la url actual después de retroceder como máximo pasos en el historial. string forward(int steps): mover pasos hacia adelante en el historial. Si sólo puede avanzar x pasos en el historial y pasos > x, avanzará sólo x pasos. Devuelve la url actual después de avanzar en el historial como máximo pasos.

Ejemplo:

Entrada:
["BrowserHistory", "visita", "visita", "visita", "atrás", "atrás", "adelante", "visita", "adelante", "atrás", "atrás"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]

Salida: [null,null,null, "facebook.com", "google.com", "facebook.com",null, "linkedin.com", "google.com", "leetcode.com"]```

Explicación:

BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com"); // Estás en "leetcode.com". Visita "google.com"
browserHistory.visit("facebook.com"); // Estás en "google.com". Visita "facebook.com"
browserHistory.visit("youtube.com"); // Estás en "facebook.com". Visita "youtube.com"
browserHistory.back(1); // Estás en "youtube.com", vuelve a "facebook.com" retornas "facebook.com"
browserHistory.back(1); // Estás en "facebook.com", vuelve a "google.com" retornas "google.com"
browserHistory.forward(1); // Estás en "google.com", avanza hasta "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com"); // Estás en "facebook.com". Visita "linkedin.com"
browserHistory.forward(2); // Estás en "linkedin.com", no puedes avanzar ningún paso.
browserHistory.back(2); // Estás en "linkedin.com", retrocede dos pasos a "facebook.com" y luego a "google.com". devuelve "google.com"
browserHistory.back(7); // Estás en "google.com", puedes retroceder sólo un paso hasta "leetcode.com". Retornas "leetcode.com"

Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

José Ramón García

Estudiante

Comparto mi solución para el problema 1

Donde podemos hacer sumas con listas enlazadas de diferentes tamaños

class Nodo:
    def __init__(self, valor, siguiente=None, anterior = None):
        self.valor = valor
        self.siguiente = siguiente 
``````python
class ListaEnlazada:
    def __init__(self, primer_nodo):
        self.cabeza = primer_nodo
        self.cola = primer_nodo
        
    def insertar_nodo_al_final(self, nuevo_nodo):
        """ Agrega un nodo al final de la lista """
        self.cola.siguiente = nuevo_nodo
        self.cola = nuevo_nodo

    def imprimir(self, nodo = None):
        if nodo is None:
            nodo = self.cabeza
        actual = nodo
        while actual:
            print(actual.valor, end=" -> ")
            actual = actual.siguiente
        print("None")

``````python
def suma(lista_1, lista_2):
    nodo_1 = lista_1.cabeza
    nodo_2 = lista_2.cabeza 
    lista_3 = ListaEnlazada(Nodo(0))
    nodo_3 = lista_3.cabeza
    suma = 0
    A = nodo_1.valor
    B = nodo_2.valor
    while nodo_1 or nodo_2:
        A = A + suma
        suma = 0
        if (A + B) < 10:
            nodo_3 = Nodo(A+B)
        else:
            suma = 1
            nodo_3 = Nodo(A+B-10)
        lista_3.insertar_nodo_al_final(nodo_3)
        
        if nodo_1.siguiente is None and nodo_2.siguiente is None:
            if suma == 0:
                break
            else:
                nodo_3 = Nodo(1)
                lista_3.insertar_nodo_al_final(nodo_3)
                break

        if nodo_1.siguiente:
            nodo_1 = nodo_1.siguiente
            A = nodo_1.valor
        else:
            A = 0

        if nodo_2.siguiente:
            nodo_2 = nodo_2.siguiente
            B = nodo_2.valor
        else:
            B = 0

    
    cabeza = lista_3.cabeza
    cabeza_siguiente = cabeza.siguiente
    cabeza.siguiente = None
    lista_3.cabeza = cabeza_siguiente

    return lista_3
``````python
def crear_lista_enlazada(valores: list):
    nodo1 = Nodo(1)
    lista = ListaEnlazada(nodo1)
    for i in valores:
        lista.insertar_nodo_al_final(Nodo(i))
    cabeza = lista.cabeza
    cabeza_siguiente = cabeza.siguiente
    cabeza.siguiente = None
    lista.cabeza = cabeza_siguiente
    lista.imprimir()
    return lista

José Ramón García

Estudiante

Solución al problema 2

    def intercambio_por_pares(self):
        if self.cabeza is None or self.cabeza.siguiente is None:
            return self.cabeza

        izq = self.cabeza
        der = izq.siguiente
        anterior = None
        self.cabeza = der

        while izq and izq.siguiente:
            der_siguiente = der.siguiente
            if der_siguiente:
                der_siguiente_siguiente = der_siguiente.siguiente

            der.siguiente, izq.siguiente = izq, der_siguiente

            if anterior:
                anterior.siguiente = der

            anterior, izq, der = izq, der_siguiente, der_siguiente_siguiente
        return self.cabeza

José Ramón García

Estudiante

Solución al problema 3

class Nodo:
    def __init__(self, valor, siguiente=None, anterior = None):
        self.valor = valor
        self.siguiente = siguiente 
        self.anterior = anterior
``````python
class BrowserHistory:

    def __init__(self, pagina: str):
        nodo = Nodo(pagina)
        self.cabeza = nodo
        self.cola = nodo
        self.actual = nodo
    
    def visit(self, pagina_a_visitar: str):

        nodo = Nodo(pagina_a_visitar)
        self.actual.siguiente = nodo
        nodo.anterior = self.actual
        print('Estabas en ', self.actual.valor, '. Ahora en ' , pagina_a_visitar)
        self.actual = nodo
        self.cola = nodo
    
    def back(self, steps: int):
        if steps<0:
            print('Favor de introducir un valor positivo')
        contador = 0
        actual = self.actual
        while actual and contador < steps:
            print('Estabas en ',actual.valor)
            anterior = actual.anterior
            if anterior is None:
                print('no puedes retroceder más, la página actual es ', actual.valor, '\n')
                break
            actual = anterior
            self.actual = actual
            print('Has retrocedido a ',actual.valor,'\n')
            contador +=1

    def forward(self, steps: int):
        if steps<0:
            print('Favor de introducir un valor positivo')
        contador = 0
        actual = self.actual
        while actual and contador < steps:
            print('Estabas en ',actual.valor)
            siguiente = actual.siguiente
            if siguiente is None:
                print('no puedes avanzar más, la página actual es ',actual.valor,'\n')
                break
            actual = siguiente
            self.actual = actual
            print('Has avanzado a ',actual.valor, '\n')
            contador +=1

Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Introducción

¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?

Lista Enlazada

Estructura de datos: Lista Enlazada

Programando listas enlazadas con Java

Cómo Invertir una Lista Enlazada

Odd Even Linked List: análisis del problema

Solución de Odd Even Linked List

Playground: Odd Even Liked List

Programando Odd Even Linked List con C++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Playground: Linked List Cycle

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de Palindrome Linked List

Playground: Palindrome Linked List

Programando Palindrome Linked List con Java

Reorder List: análisis del problema

Solución de Reorder List

Programando Reorder List con JavaScript

Playground: Reorder List Without Repeated Values

Reto: LRU Caché