Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

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

Ejercicios resueltos 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.

 class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next
class Solution:
   def sumarDosNumeros(self, nodo1: ListNode, nodo2: ListNode) -> ListNode:
       cabezaTemporal = ListNode()
       apuntador1 = nodo1
       apuntador2 = nodo2
       nodoActual = cabezaTemporal
       lleva = 0
       while apuntador1 or apuntador2:
           x = apuntador1.val if apuntador1 else 0
           y = apuntador2.val if apuntador2 else 0

           current_sum = lleva + x + y
          
           lleva = current_sum // 10
           nodoActual.next = ListNode(current_sum % 10)
           nodoActual = nodoActual.next
          
           if apuntador1: apuntador1 = apuntador1.next
           if apuntador2: apuntador2 = apuntador2.next
      
       if lleva: nodoActual.next = ListNode(lleva)
       return cabezaTemporal.next

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]

 # Definition for singly-linked list.

 class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next
class Solution:
   def swapPairs(self, cabeza: ListNode) -> ListNode:
       nodoActual = cabeza
       if nodoActual == None :
           return None
       while nodoActual != None and nodoActual.next != None:

           if nodoActual.val == nodoActual.next.val:
               nodoActual = nodoActual.next.next
           else:
               nodoActual.val, nodoActual.next.val = nodoActual.next.val, nodoActual.val
               nodoActual = nodoActual.next.next
       return cabeza

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"

class BrowserHistory:
   def __init__(self, homepage: str):
       self.home = homepage
       self.main = []
       self.temporal = []
 
   def visit(self, url: str) -> None:
       self.main.append(url)
       if self.temporal :
           self.temporal.clear()
 
   def back(self, pasos: int) -> str:
       while(self.main and pasos):
           pasos -= 1
           x = self.main.pop()
           self.temporal.append(x)
       if self.main:
           return self.main[-1]
       return self.home   
 
   def forward(self, pasos: int) -> str:
       while(self.temporal and pasos):
           pasos -= 1
           x = self.temporal.pop()
           self.main.append(x)
       if self.main:
           return self.main[-1]
       return self.home

 class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next
class Solution:
   def sumarDosNumeros(self, nodo1: ListNode, nodo2: ListNode) -> ListNode:
       cabezaTemporal = ListNode()
       apuntador1 = nodo1
       apuntador2 = nodo2
       nodoActual = cabezaTemporal
       lleva = 0
       while apuntador1 or apuntador2:
           x = apuntador1.val if apuntador1 else 0
           y = apuntador2.val if apuntador2 else 0

           current_sum = lleva + x + y
          
           lleva = current_sum // 10
           nodoActual.next = ListNode(current_sum % 10)
           nodoActual = nodoActual.next
          
           if apuntador1: apuntador1 = apuntador1.next
           if apuntador2: apuntador2 = apuntador2.next
      
       if lleva: nodoActual.next = ListNode(lleva)
       return cabezaTemporal.next
          

 # Definition for singly-linked list.

 class ListNode:
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next
class Solution:
   def swapPairs(self, cabeza: ListNode) -> ListNode:
       nodoActual = cabeza
       if nodoActual == None :
           return None
       while nodoActual != None and nodoActual.next != None:

           if nodoActual.val == nodoActual.next.val:
               nodoActual = nodoActual.next.next
           else:
               nodoActual.val, nodoActual.next.val = nodoActual.next.val, nodoActual.val
               nodoActual = nodoActual.next.next
       return cabeza

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 BrowserHistory:
   def __init__(self, homepage: str):
       self.home = homepage
       self.main = []
       self.temporal = []
 
   def visit(self, url: str) -> None:
       self.main.append(url)
       if self.temporal :
           self.temporal.clear()
 
   def back(self, pasos: int) -> str:
       while(self.main and pasos):
           pasos -= 1
           x = self.main.pop()
           self.temporal.append(x)
       if self.main:
           return self.main[-1]
       return self.home   
 
   def forward(self, pasos: int) -> str:
       while(self.temporal and pasos):
           pasos -= 1
           x = self.temporal.pop()
           self.main.append(x)
       if self.main:
           return self.main[-1]
       return self.home 

Juan Pablo Reina Gutierrez

student•

En el último ejercicio hice un método que permite imprimir los elementos del historial resaltando la página actual:

Se ve algo así cuando se ejecuta:

Nicolas Alpargatero

El último ejercicio creo que no iría dentro de los ejercicios. 🫠🤓 pero tremendo! . Qué bueno que subió las respuestas en python.

La solución del segundo ejercicio modifica los valores de los nodos, pero no los apuntadores, sirve, pero no cumpliría totalmente la solución al ejercicio.

Carlos Hernandez

Y tampoco se está invirtiendo

Operaciones con Listas Enlazadas: Suma, Intercambio y 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