Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Clase 22 de 41 • Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

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"

Juan Pablo Reina Gutierrez

student•

Pregunta, ¿la implementación del historial de navegación se podría hacer con una lista doblemente enlazada?

José Ramón García

student•

Así es :)

Creo que es necesario para poder hacer la función back

José Ramón García

student•

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

student•

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

student•

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

Santiago Amaya

student•

def rever_sum(l1: Node, l2: Node) -> Lista:
    # Revertir las listas enlazadas
    l1.reverse()
    l2.reverse()

    # Inicializar variables para la suma y el acarreo
    carry = 0
    result = Lista()

    # Sumar los nodos correspondientes de las dos listas
    current_l1 = l1.head
    current_l2 = l2.head
    while current_l1 or current_l2 or carry:
        value = carry
        if current_l1:
            value += current_l1.data
            current_l1 = current_l1.next
        if current_l2:
            value += current_l2.data
            current_l2 = current_l2.next

        # Calcular el dígito y el nuevo acarreo
        digit = value % 10
        carry = value // 10

        # Agregar el dígito al resultado
        result.append(digit)

    # Revertir el resultado para obtener la suma correcta
    result.reverse()

    return result
```def rever\_sum(l1: Node, l2: Node) -> Lista:    # Revertir las listas enlazadas    l1.reverse()    l2.reverse()
    # Inicializar variables para la suma y el acarreo    carry = 0    result = Lista()
    # Sumar los nodos correspondientes de las dos listas    current\_l1 = l1.head    current\_l2 = l2.head    while current\_l1 or current\_l2 or carry:        value = carry        if current\_l1:            value += current\_l1.data            current\_l1 = current\_l1.next        if current\_l2:            value += current\_l2.data            current\_l2 = current\_l2.next
        # Calcular el dígito y el nuevo acarreo        digit = value % 10        carry = value // 10
        # Agregar el dígito al resultado        result.append(digit)
    # Revertir el resultado para obtener la suma correcta    result.reverse()
    return result

Santiago Amaya

student•

def rever_sum(l1:Node, l2:Node):
    """243 + 564 = 807""" 
    ## returne both lists
    current = l1.head
    current_l2 = l2.head
    while current and current_l2:
        current = current.next
        current_l2 = current_l2.next
    prev = None
    prev_l2 = None
    while current and current_l2:
        current.next, current, prev = prev, current.next, current
        current_l2.next, current_l2, prev_l2 = prev_l2, current_l2.next, current_l2
    curent = prev
    current_l2 = prev_l2
    ## get the data as string and the get in to number
    result = []
    result_l2 = []
    current = l1.head
    current_l2 = l2.head
    while current and current_l2:
        result_l2.append(str(current_l2))
        result.append(str(current))
        current, current_l2 = current.next, current_l2.next
    suma = int(''.join(result))+int(''.join(result_l2)) 
    return suma 
```Aquí mi solución del primero &#x20;

Nicolas Alpargatero

student•

Buenos los ejercicios. En el primera es aplicar la propiedad conmutativa. En el segundo era muy similar al de pares del módulo. En último, del historial realmente la solución óptima es con listas no con double linked list. . Aquí el del historial con linked list, pues ayuda entender mejor:

er ff

student•

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"]```

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"

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

    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

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
    

def rever_sum(l1: Node, l2: Node) -> Lista:
    # Revertir las listas enlazadas
    l1.reverse()
    l2.reverse()

    # Inicializar variables para la suma y el acarreo
    carry = 0
    result = Lista()

    # Sumar los nodos correspondientes de las dos listas
    current_l1 = l1.head
    current_l2 = l2.head
    while current_l1 or current_l2 or carry:
        value = carry
        if current_l1:
            value += current_l1.data
            current_l1 = current_l1.next
        if current_l2:
            value += current_l2.data
            current_l2 = current_l2.next

        # Calcular el dígito y el nuevo acarreo
        digit = value % 10
        carry = value // 10

        # Agregar el dígito al resultado
        result.append(digit)

    # Revertir el resultado para obtener la suma correcta
    result.reverse()

    return result
```def rever\_sum(l1: Node, l2: Node) -> Lista:    # Revertir las listas enlazadas    l1.reverse()    l2.reverse()
    # Inicializar variables para la suma y el acarreo    carry = 0    result = Lista()
    # Sumar los nodos correspondientes de las dos listas    current\_l1 = l1.head    current\_l2 = l2.head    while current\_l1 or current\_l2 or carry:        value = carry        if current\_l1:            value += current\_l1.data            current\_l1 = current\_l1.next        if current\_l2:            value += current\_l2.data            current\_l2 = current\_l2.next
        # Calcular el dígito y el nuevo acarreo        digit = value % 10        carry = value // 10
        # Agregar el dígito al resultado        result.append(digit)
    # Revertir el resultado para obtener la suma correcta    result.reverse()
    return result

def rever_sum(l1:Node, l2:Node):
    """243 + 564 = 807""" 
    ## returne both lists
    current = l1.head
    current_l2 = l2.head
    while current and current_l2:
        current = current.next
        current_l2 = current_l2.next
    prev = None
    prev_l2 = None
    while current and current_l2:
        current.next, current, prev = prev, current.next, current
        current_l2.next, current_l2, prev_l2 = prev_l2, current_l2.next, current_l2
    curent = prev
    current_l2 = prev_l2
    ## get the data as string and the get in to number
    result = []
    result_l2 = []
    current = l1.head
    current_l2 = l2.head
    while current and current_l2:
        result_l2.append(str(current_l2))
        result.append(str(current))
        current, current_l2 = current.next, current_l2.next
    suma = int(''.join(result))+int(''.join(result_l2)) 
    return suma 
```Aquí mi solución del primero &#x20;

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é

Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

Pilas y colas

Estructura de datos: Pilas y Colas

Paréntesis Válido: análisis del problema

Solución de Paréntesis Válido

Playground: Paréntesis Válido

Programando Paréntesis Válido con C++

Comparación de Cadenas con Backspaces

Colas de prioridad

Estructura de datos: Colas de Prioridad

K Closest Points to Origin: análisis del problema

Solución de K Closest Points to Origin

Playground: K Closest Points to Origin

Programando K Closest Points to Origin con Python

Reorganize String: análisis del problema

Solución de Reorganize String

Playground: Reorganize String

Programando Reorganize String con Python

Colas de Prioridad: Ejercicios Prácticos y Soluciones

Colas de Prioridad y Gestión de Eventos

Próximos pasos

Toma el Curso Avanzado de Algoritmos: Grafos y Árboles