Introdução
Bem-vindos ao 13º artigo da série Preparação para Entrevistas no blog A Arte de Programar. Hoje, vamos explorar um desafio que se destaca como um dos mais solicitados em entrevistas de programação, conforme listado no LeetCode: Add Two Numbers.
Neste artigo, detalharemos o problema sobre somar números em Lista Encadeadas, seguido de soluções implementadas em Java e Python. Além disso, realizaremos uma análise detalhada da complexidade de tempo e espaço do algoritmo.
Vamos começar!
Explicação do Problema
O problema envolve a soma de dois números que são representados por duas listas encadeadas. Cada nó dessas listas contém um único dígito, e os dígitos estão armazenados em ordem inversa. Esta estrutura permite que a soma seja realizada da mesma maneira que fazemos manualmente, começando pelos dígitos menos significativos (os ‘dígitos das unidades’) e avançando para os mais significativos, lidando com qualquer ‘vai um‘ que ocorra.
Veja o exemplo abaixo:
Suponha que temos dois números, 759 e 246. Nas listas encadeadas, o número 759 seria representado como 9 -> 5 -> 7, e o número 246 como 6 -> 4 -> 2. Quando somamos esses números, obtemos 1005, que seria representado pela lista encadeada 5 -> 0 -> 0 -> 1.
Este exemplo demonstra como lidamos com dígitos individualmente e como o ‘vai um’ é propagado ao longo da soma.
O problema é um teste excelente para habilidades em manipulação de listas encadeadas e compreensão de operações numéricas básicas.”
Implementação em Java e Python
Vamos então explorar uma solução em Java e Python para o problema de adicionar dois números representados por listas encadeadas(Add Two Numbers). Este código considera a inversão dos dígitos e a propagação do ‘vai um’, criando uma nova lista encadeada que representa a soma dos números.
class SomaNumeros {
public static No somaDuasListas(No lista1, No lista2) {
No frente = new No(0);
No noAtual = frente;
int vaiUm = 0;
while (lista1 != null || lista2 != null || vaiUm > 0) {
int n1 = lista1 == null ? 0 : lista1.valor;
int n2 = lista2 == null ? 0 : lista2.valor;
int sum = n1 + n2 + vaiUm;
vaiUm = sum / 10;
noAtual.proximo = new No(sum % 10);
noAtual = noAtual.proximo;
lista1 = lista1 != null ? lista1.proximo : null;
lista2 = lista2 != null ? lista2.proximo : null;
}
return frente.proximo;
}
}
class No {
int valor;
No proximo;
No(int valor) {
this.valor = valor;
}
}
Explicação do Código
class No:
def __init__(self, valor=0, proximo=None):
self.valor = valor
self.proximo = proximo
def soma_duas_listas(lista1, lista2):
frente = No(0)
no_atual = frente
vai_um = 0
while lista1 or lista2 or vai_um:
n1 = lista1.valor if lista1 else 0
n2 = lista2.valor if lista2 else 0
soma = n1 + n2 + vai_um
vai_um = soma // 10
no_atual.proximo = No(soma % 10)
no_atual = no_atual.proximo
lista1 = lista1.proximo if lista1 else None
lista2 = lista2.proximo if lista2 else None
return frente.proximo
# Exemplo de uso:
# Lista 1: 2 -> 4 -> 3 (representando o número 342)
# Lista 2: 5 -> 6 -> 4 (representando o número 465)
# Criando a primeira lista encadeada
nodo1_1 = No(9)
nodo1_2 = No(5)
nodo1_3 = No(7)
nodo1_1.proximo = nodo1_2
nodo1_2.proximo = nodo1_3
# Criando a segunda lista encadeada
nodo2_1 = No(6)
nodo2_2 = No(4)
nodo2_3 = No(2)
nodo2_1.proximo = nodo2_2
nodo2_2.proximo = nodo2_3
# Somando as duas listas
resultado = soma_duas_listas(nodo1_1, nodo2_1)
# Imprimindo o resultado
no_atual = resultado
while no_atual:
print(no_atual.valor, end=" -> ")
no_atual = no_atual.proximo
# A saída esperada é 7 -> 0 -> 8 (representando o número 807)
- O método
somaDuasListascria inicialmente um nó(frente) apontando para o primeiro elemento da lista, facilitando sua manipulação e evitando verificações especiais para o primeiro nó. - Dentro do laço
while, verificamos se ainda existem nós para processar em ambas as listas ou se há um ‘vai um’ remanescente. - Calculamos a soma dos valores atuais (
n1en2) de cada lista, junto com o ‘vai um’ anterior. - O ‘vai um’ para a próxima iteração é determinado pela divisão da soma atual por 10(
vaiUm = sum / 10). - Um novo nó com o valor do dígito menos significativo da soma (
sum % 10) é criado e anexado à lista resultante. - Avançamos nas listas de entrada movendo
lista1elista2para seus respectivos próximos nós. - Após o término do laço, se ainda houver um ‘vai um’, adicionamos um novo nó ao final da lista resultante.
- O resultado da soma é a lista encadeada que começa no nó seguinte ao nó cabeça temporário, pois este foi apenas um marcador inicial para evitar checagens especiais.
Lista com Tamanhos Diferentes
A implementação pode lidar com listas de comprimentos variados de forma eficiente. Se uma lista for mais longa que a outra, o algoritmo continua a processar os nós remanescentes, garantindo que cada dígito seja considerado e que o ‘vai um’ não seja perdido.
Por exemplo: a primeira lista representa o número 513 (armazenado como 3 -> 1 -> 5) e a segunda lista representa o número 29 (armazenado como 9 -> 2). A lista mais longa tem um dígito adicional para ser processado após o final da lista mais curta.
Análise de Complexidade
Complexidade de Tempo
No nosso código, o loop principal executa uma vez para cada elemento nas duas listas encadeadas. Portanto, se ‘n’ é o número de elementos na lista mais longa, nosso algoritmo terá uma complexidade de tempo de O(n). Isso significa que o tempo necessário para realizar a soma é proporcional ao tamanho da lista mais longa.
Complexidade de Espaço
No nosso algoritmo, a memória é consumida principalmente pela nova lista encadeada que representa o número resultante da soma. Portanto, a complexidade de espaço também será O(n), pois no pior caso, pode haver um ‘vai um’ que resulta em um nó adicional. Assim, para listas de tamanho ‘n’, precisaremos de espaço para ‘n + 1’ nós.
Em resumo, nosso algoritmo é linear tanto em tempo quanto em espaço.
Conclusão
Chegamos ao final do nosso 13º artigo da série ‘Preparação para Entrevistas‘. Hoje discutimos a o problema de somar números representados por listas encadeadas(Add Two Numbers), um problema muito comum em entrevistas. Esperamos que as soluções e análises apresentadas aqui tenham ampliado seu entendimento sobre este problema.
Se você achou este artigo útil, não deixe de explorar os outros artigos da série. Cada um deles é projetado para fornecer insights valiosos e práticos sobre diferentes problemas e técnicas de programação.
Além disso, este artigo também está disponível em inglês! Confira a versão em inglês no meu blog e amplie seu aprendizado em outro idioma. Aqui, você pode ler o artigo em Inglês.
👉 Fique atento para mais conteúdos e não esqueça de compartilhar sua experiência nos comentários. Qual é o próximo tópico que você gostaria de ver explorado? Estamos ansiosos para continuar essa jornada de aprendizado junto com você!