Cursos Empresas Blog Live Conf Eventos Precios

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

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Clase 19 de 34

Clase 19 / 34

 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 

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

Progreso del curso

Introducción

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos