class Nodo:
    def __init__(self, nombre, habitacion):
        self.nombre = nombre        # Nombre del cliente
        self.habitacion = habitacion  # Número de habitación del cliente
        self.siguiente = None      # Puntero al siguiente nodo en la lista

class ListaEnlazada:
    def __init__(self):
        self.cabeza = None   # Inicialmente la lista está vacía

    def agregar_cliente(self, nombre, habitacion):
        nuevo_nodo = Nodo(nombre, habitacion)
        if self.cabeza is None:
            # Si la lista está vacía, inserta el nuevo nodo como cabeza
            self.cabeza = nuevo_nodo
        else:
            actual = self.cabeza
            # Insertar antes de la cabeza si el nuevo nodo debe ir al principio
            if nuevo_nodo.nombre < actual.nombre:
                nuevo_nodo.siguiente = actual
                self.cabeza = nuevo_nodo
            else:
                # Recorrer la lista para encontrar la posición correcta
                # se compara que el nodo actual sea menor alfabéticamente que el nuevo nodo.
                while actual.siguiente is not None and actual.siguiente.nombre < nuevo_nodo.nombre:  
                    actual = actual.siguiente
                nuevo_nodo.siguiente = actual.siguiente
                actual.siguiente = nuevo_nodo

    def obtener_clientes_ordenados(self):
        clientes = [] #Arreglo para guardar lo datos de cada nodo de la lista
        actual = self.cabeza
        # Recorrer la lista y recolectar información de cada cliente
        while actual is not None:
            clientes.append(f"Cliente: {actual.nombre}, Habitación: {actual.habitacion}")
            actual = actual.siguiente
        return clientes

# Ejemplo de uso de la lista enlazada para manejar clientes de un hotel
clientes_hotel = ListaEnlazada()
clientes_hotel.agregar_cliente("Pedro Bonilla", 105)
clientes_hotel.agregar_cliente("Carlos Fonseca", 102)
clientes_hotel.agregar_cliente("Karla Herrera", 201)

# Imprimir la lista de clientes ordenados alfabéticamente
print("\n".join(clientes_hotel.obtener_clientes_ordenados()))