Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

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