- Encontro de Listas Ligadas
Dado os nós de cabeçalho de duas listas ligadas, headA e headB, encontre e retorne o nó de início da interseção. Se as duas listas não tiverem nó de interseção, retorne null.
Presume-se que a estrutura da lista ligada não contenha ciclos.
Solução com Tabela Hash
Uma abordagem direta é usar uma tabela hash para armazenar os nós de uma lista enquanto a percorremos. Em seguida, percorremos a segunda lista e, para cada nó, verificamos se ele já existe na tabela hash. O primeiro nó encontrado na tabela hash é o nó de interseção.
#include <unordered_set>
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode *encontrarInterseccao(ListNode *headA, ListNode *headB) {
std::unordered_set<ListNode*> nosVistos;
ListNode* atualA = headA;
while (atualA != nullptr) {
nosVistos.insert(atualA);
atualA = atualA->next;
}
ListNode* atualB = headB;
while (atualB != nullptr) {
if (nosVistos.count(atualB)) {
return atualB; // Encontrou o nó de interseção
}
atualB = atualB->next;
}
return nullptr; // Nenhuma interseção encontrada
}
Solução com Ponteiros Duplos (Abordagem O(1) de Espaço)
Esta abordagem utiliza dois ponteiros, um para cada lista. Quando um ponteiro atinge o final de sua lista, ele é redirecionado para o início da outra lista. Se as listas se cruzarem, os ponteiros eventualmente se encontrarão no nó de interseção. Se não houver interseção, eles se encontrarão em null após percorerem ambas as listas.
A intuição é que, ao trocar as listas quando um ponteiro atinge o fim, ambos os ponteiros percorrem a mesma distância total (comprimento da lista A + comprimento da lista B) antes de se encontrarem, caso haja uma interseção. Se não houver interseção, ambos percorrerão um total de len(A) + len(B) nós e terminarão em nullptr.
ListNode *encontrarInterseccaoComPonteiros(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode* ponteiroA = headA;
ListNode* ponteiroB = headB;
// Continue até que os ponteiros se encontrem
// Se houver interseção, eles se encontrarão no nó de interseção.
// Se não houver interseção, eles se encontrarão em nullptr (depois de percorrerem ambas as listas).
while (ponteiroA != ponteiroB) {
// Se ponteiroA chegar ao fim de A, redirecione para headB, caso contrário, avance.
ponteiroA = (ponteiroA == nullptr) ? headB : ponteiroA->next;
// Se ponteiroB chegar ao fim de B, redirecione para headA, caso contrário, avance.
ponteiroB = (ponteiroB == nullptr) ? headA : ponteiroB->next;
}
// ponteiroA (ou ponteiroB) é o nó de interseção, ou nullptr se não houver interseção.
return ponteiroA;
}
- Inverter Lista Ligada
Dada a cabeça de uma lista ligada, inverta a lista e retorne a cabeça invertida.
Solução Iterativa
Iteramos pela lista, mantendo três ponteiros: anterior, atual e proximo. Em cada passo, alteramos o ponteiro next do nó atual para apontar para anterior, e então avançamos os ponteiros.
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* inverterListaIterativa(ListNode* cabeca) {
ListNode* anterior = nullptr;
ListNode* atual = cabeca;
while (atual != nullptr) {
ListNode* proximoTemporario = atual->next; // Salva o próximo nó
atual->next = anterior; // Inverte o ponteiro 'next'
anterior = atual; // Avança o ponteiro 'anterior'
atual = proximoTemporario; // Avança o ponteiro 'atual'
}
return anterior; // 'anterior' agora é a nova cabeça
}
Solução Recursiva
A ideia recursiva é inverter o restante da lista (head->next) primeiro, e depois conectar o nó atual ao final da lista invertida.
ListNode* inverterListaRecursiva(ListNode* cabeca) {
// Caso base: lista vazia ou com um único nó
if (cabeca == nullptr || cabeca->next == nullptr) {
return cabeca;
}
// Inverte o restante da lista
ListNode* novaCabeca = inverterListaRecursiva(cabeca->next);
// Conecta o nó atual ao final da lista invertida
cabeca->next->next = cabeca;
cabeca->next = nullptr; // O nó original 'cabeca' se torna o último nó
return novaCabeca; // Retorna a nova cabeça da lista invertida
}
- Palíndromo de Lista Ligada
Dado a cabeça de uma lista ligada, determine se ela é um palíndromo.
Solução Usando Simulação de Array
A maneira mais simples é copiar os valores da lista ligada para um array e depois verificar se o array é um palíndromo usando dois ponteiros.
#include <vector>
#include <algorithm>
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
bool ehPalindromoComArray(ListNode* cabeca) {
std::vector<int> valores;
ListNode* atual = cabeca;
while (atual != nullptr) {
valores.push_back(atual->val);
atual = atual->next;
}
int esquerda = 0;
int direita = valores.size() - 1;
while (esquerda < direita) {
if (valores[esquerda] != valores[direita]) {
return false;
}
esquerda++;
direita--;
}
return true;
}
Solução Encontrando o Meio, Invertendo a Segunda Metade e Comparando (O(1) Espaço)
Esta solução envolve encontrar o nó do meio da lista, inverter a segunda metade da lista e, em seguida, comparar a primeira metade com a segunda metade invertida.
// Função auxiliar para encontrar o nó do meio (retorna o primeiro meio em caso de par)
ListNode* encontrarMeio(ListNode* cabeca) {
ListNode* lento = cabeca;
ListNode* rapido = cabeca;
while (rapido != nullptr && rapido->next != nullptr) {
lento = lento->next;
rapido = rapido->next->next;
}
return lento;
}
// Função auxiliar para inverter a lista ligada (mesma que 206)
ListNode* inverterLista(ListNode* cabeca) {
ListNode* anterior = nullptr;
ListNode* atual = cabeca;
while (atual != nullptr) {
ListNode* proximoTemporario = atual->next;
atual->next = anterior;
anterior = atual;
atual = proximoTemporario;
}
return anterior;
}
bool ehPalindromoO1Espaco(ListNode* cabeca) {
if (cabeca == nullptr || cabeca->next == nullptr) {
return true;
}
// 1. Encontrar o meio da lista
ListNode* meio = encontrarMeio(cabeca);
// 2. Inverter a segunda metade da lista a partir do meio
ListNode* segundaMetadeInvertida = inverterLista(meio);
// 3. Comparar a primeira metade com a segunda metade invertida
ListNode* ponteiro1 = cabeca;
ListNode* ponteiro2 = segundaMetadeInvertida;
bool ehPalindromo = true;
while (ponteiro2 != nullptr) { // Compara até o fim da segunda metade invertida
if (ponteiro1->val != ponteiro2->val) {
ehPalindromo = false;
break;
}
ponteiro1 = ponteiro1->next;
ponteiro2 = ponteiro2->next;
}
// Opcional: Restaurar a lista ligada (invertendo a segunda metade de volta)
// inverterLista(segundaMetadeInvertida);
return ehPalindromo;
}
- Lista Ligada com Ciclo
Dado a cabeça de uma lista ligada, determine se a lista ligada tem um ciclo.
Solução com Tabela Hash
Percorra a lista ligada e armazene cada nó visitado em uma tabela hash. Se você encontrar um nó que já esteja na tabela hash, significa que há um ciclo.
#include <unordered_set>
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
bool temCicloComHash(ListNode *cabeca) {
std::unordered_set<ListNode*> nosVistos;
ListNode* atual = cabeca;
while (atual != nullptr) {
if (nosVistos.count(atual)) {
return true; // Encontrado um nó que já foi visitado
}
nosVistos.insert(atual);
atual = atual->next;
}
return false; // Chegou ao fim sem encontrar ciclos
}
Solução com Ponteiros Lento e Rápido (Floyd's Cycle-Finding Algorithm)
Use dois ponteiros, um lento (move um passo de cada vez) e um rápido (move dois passos de cada vez). Se houver um ciclo, o ponteiro rápido eventualmente alcançará o ponteiro lento.
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
bool temCicloComPonteiros(ListNode *cabeca) {
if (cabeca == nullptr || cabeca->next == nullptr) {
return false; // Lista vazia ou com um único nó não pode ter ciclo
}
ListNode* lento = cabeca;
ListNode* rapido = cabeca;
while (rapido != nullptr && rapido->next != nullptr) {
lento = lento->next; // Move um passo
rapido = rapido->next->next; // Move dois passos
if (lento == rapido) {
return true; // Os ponteiros se encontraram, há um ciclo
}
}
return false; // O ponteiro rápido chegou ao fim, sem ciclo
}
- Lista Ligada com Ciclo II
Dado a cabeça de uma lista ligada, retorne o nó onde o ciclo começa. Se não houver ciclo, retorne null.
Solução com Tabela Hash
Similar à detecção de ciclo, armazene os nós visitados. O primeiro nó encontrado que já está na tabela hash é o início do ciclo.
#include <unordered_set>
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode *encontrarInicioCicloHash(ListNode *cabeca) {
std::unordered_set<ListNode*> nosVistos;
ListNode* atual = cabeca;
while (atual != nullptr) {
if (nosVistos.count(atual)) {
return atual; // Este é o nó de início do ciclo
}
nosVistos.insert(atual);
atual = atual->next;
}
return nullptr; // Sem ciclo
}
Solução com Ponteiros Lento e Rápido (Extensão do Algoritmo de Floyd)
Primeiro, detecte a presença de um ciclo usando os ponteiros lento e rápido. Se um ciclo for detectado, mova um ponteiro de volta para a cabeça da lista e mantenha o outro ponteiro no ponto de encontro. Mova ambos os ponteiros um passo de cada vez. O ponto onde eles se encontram novamente é o início do ciclo.
Prova Rápida: Seja a a distância da cabeça até o início do ciclo, b a distância do início do ciclo até o ponto de encontro, e c a distância do ponto de encontro de volta ao início do ciclo. O comprimento total do ciclo é L = b + c. Quando os ponteiros se encontram, o ponteiro lento percorreu a + b e o pontiero rápido percorreu a + b + k*L (para algum inteiro k >= 1). Como o ponteiro rápido é o dobro da velocidade do lento, temos: 2 * (a + b) = a + b + k*L. Simplificando, obtemos a + b = k*L, ou a = k*L - b. Isso significa que a distância a da cabeça até o início do ciclo é igual à distância do ponto de encontro até o início do ciclo (k*L - b é equivalente a percorrer o ciclo k vezes e depois voltar b passos, o que te leva ao início do ciclo).
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode *encontrarInicioCicloPonteiros(ListNode *cabeca) {
if (cabeca == nullptr || cabeca->next == nullptr) {
return nullptr;
}
ListNode* lento = cabeca;
ListNode* rapido = cabeca;
bool cicloEncontrado = false;
// 1. Detectar o ciclo e encontrar o ponto de encontro
while (rapido != nullptr && rapido->next != nullptr) {
lento = lento->next;
rapido = rapido->next->next;
if (lento == rapido) {
cicloEncontrado = true;
break;
}
}
// 2. Se um ciclo foi encontrado, encontrar o nó de início do ciclo
if (cicloEncontrado) {
ListNode* ponteiro1 = cabeca;
ListNode* ponteiro2 = lento; // Ou rapido, pois ambos estão no ponto de encontro
while (ponteiro1 != ponteiro2) {
ponteiro1 = ponteiro1->next;
ponteiro2 = ponteiro2->next;
}
return ponteiro1; // O ponto onde eles se encontram é o início do ciclo
}
return nullptr; // Nenhum ciclo encontrado
}
- Mesclar Duas Listas Ligadas Ordenadas
Mescle duas listas ligadas ordenadas em uma única lista ligada ordenada.
Solução Recursiva
A abodragem recursiva compara os nós de cabeça das duas listas e recursivamente mescla o restante.
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* mesclarDuasListasRecursiva(ListNode* list1, ListNode* list2) {
// Casos base: se uma lista for vazia, retorne a outra
if (list1 == nullptr) {
return list2;
}
if (list2 == nullptr) {
return list1;
}
// Compara os valores dos nós de cabeça
if (list1->val < list2->val) {
// Se list1->val for menor, recursivamente mescla o restante de list1 com list2
list1->next = mesclarDuasListasRecursiva(list1->next, list2);
return list1; // Retorna o nó menor como a nova cabeça
} else {
// Se list2->val for menor ou igual, recursivamente mescla list1 com o restante de list2
list2->next = mesclarDuasListasRecursiva(list1, list2->next);
return list2; // Retorna o nó menor como a nova cabeça
}
}
Solução Iterativa
Crie um nó sentinela (cabeça fictícia) e use um ponteiro para construir a nova lista mesclada. Compare os nós atuais das duas listas e anexe o menor ao resultado.
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* mesclarDuasListasIterativa(ListNode* list1, ListNode* list2) {
// Nó sentinela para simplificar a lógica
ListNode* sentinela = new ListNode(0);
ListNode* ponteiroAtual = sentinela;
// Percorre ambas as listas enquanto ambas não estiverem vazias
while (list1 != nullptr && list2 != nullptr) {
if (list1->val < list2->val) {
ponteiroAtual->next = list1;
list1 = list1->next;
} else {
ponteiroAtual->next = list2;
list2 = list2->next;
}
ponteiroAtual = ponteiroAtual->next;
}
// Anexa o restante da lista não vazia
if (list1 != nullptr) {
ponteiroAtual->next = list1;
} else {
ponteiroAtual->next = list2;
}
// Retorna a cabeça da lista mesclada (ignorando o sentinela)
return sentinela->next;
}
- Somar Dois Números Representados por Listas Ligadas
Você recebe duas listas ligadas não vazias que representam dois números inteiros não negativos. Os dígitos são armazenados em ordem inversa e cada nó contém um único dígito. Some os dois números e retorne a soma como uma lista ligada.
Solução Otimizada
Iteramos pelas duas listas e calculamos a soma dígito por dígito, incluindo o transporte (carry). Criamos uma nova lista para armazenar o resultado.
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {} // Construtor adicional
};
ListNode* somarDoisNumeros(ListNode* l1, ListNode* l2) {
int somaTransporte = 0;
ListNode* cabecaResultado = new ListNode(0); // Nó sentinela para o resultado
ListNode* atualResultado = cabecaResultado;
ListNode* atual1 = l1;
ListNode* atual2 = l2;
// Continua enquanto houver dígitos em qualquer lista ou houver transporte
while (atual1 != nullptr || atual2 != nullptr || somaTransporte != 0) {
int valor1 = (atual1 != nullptr) ? atual1->val : 0;
int valor2 = (atual2 != nullptr) ? atual2->val : 0;
int somaAtual = valor1 + valor2 + somaTransporte;
somaTransporte = somaAtual / 10; // Calcula o novo transporte
int digito = somaAtual % 10; // Calcula o dígito para o nó atual
// Cria um novo nó para o resultado
atualResultado->next = new ListNode(digito);
atualResultado = atualResultado->next;
// Avança os ponteiros das listas de entrada, se existirem
if (atual1 != nullptr) {
atual1 = atual1->next;
}
if (atual2 != nullptr) {
atual2 = atual2->next;
}
}
return cabecaResultado->next; // Retorna a cabeça da lista de resultado real
}
- Remover N-ésimo Nó da Lista do Fim
Dada a cabeça de uma lista ligada, remova o n-ésimo nó da lista a partir do final e retorne sua cabeça.
Solução com Dois Passos (Calcular Comprimento)
Primeiro, percorra a lista para encontrar seu comprimento. Em seguida, calcule a posição do nó a ser removido a partir do início (comprimento - n) e percorra novamente para removê-lo.
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* removerNthDoFimDoisPassos(ListNode* cabeca, int n) {
int comprimento = 0;
ListNode* atual = cabeca;
// Primeiro passo: Calcular o comprimento da lista
while (atual != nullptr) {
comprimento++;
atual = atual->next;
}
// Calcula a posição do nó a ser removido a partir do início
int posParaRemover = comprimento - n;
// Se o nó a ser removido for a cabeça
if (posParaRemover == 0) {
return cabeca->next;
}
// Segundo passo: Percorrer até o nó ANTERIOR ao nó a ser removido
atual = cabeca;
for (int i = 0; i < posParaRemover - 1; ++i) {
atual = atual->next;
}
// Remove o nó
ListNode* noParaRemover = atual->next;
atual->next = noParaRemover->next;
// delete noParaRemover; // Liberar memória é opcional dependendo do ambiente
return cabeca;
}
Solução com Ponteiros Lento e Rápido (Um Passo)
Use dois ponteiros, rapido e lento. Avance o ponteiro rapido n passos à frente. Em seguida, avance ambos os ponteiros simultaneamente até que rapido atinja o final da lista. Nesse ponto, lento estará apontando para o nó anterior ao nó a ser removido.
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* removerNthDoFimUmPasso(ListNode* cabeca, int n) {
// Cria um nó sentinela para lidar com o caso de remoção da cabeça
ListNode* sentinela = new ListNode(0, cabeca);
ListNode* rapido = sentinela;
ListNode* lento = sentinela;
// Avança o ponteiro rápido n+1 passos
// (n+1 para que 'lento' aponte para o nó ANTES do nó a ser removido)
for (int i = 0; i <= n; ++i) {
if (rapido == nullptr) {
// Isso não deveria acontecer se n for válido (1 <= n <= sz)
// Mas é uma boa prática de robustez.
return cabeca;
}
rapido = rapido->next;
}
// Avança ambos os ponteiros até que 'rapido' chegue ao fim
while (rapido != nullptr) {
lento = lento->next;
rapido = rapido->next;
}
// 'lento' agora aponta para o nó anterior ao que precisa ser removido
ListNode* noParaRemover = lento->next;
lento->next = noParaRemover->next;
// delete noParaRemover; // Liberar memória é opcional
ListNode* resultado = sentinela->next;
// delete sentinela; // Liberar memória do sentinela
return resultado;
}
- Trocar Pares de Nós na Lista Ligada
Dada a cabeça de uma lista ligada, troque os nós adjacentes e retorne a cabeça modificada.
Solução Recursiva
A ideia é trocar os dois primeiros nós, e então recursivamente chamar a função para o restante da lista (a partir do terceiro nó).
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* trocarParesRecursiva(ListNode* cabeca) {
// Caso base: lista vazia ou com um único nó
if (cabeca == nullptr || cabeca->next == nullptr) {
return cabeca;
}
// Nós que precisam ser trocados
ListNode* primeiroNo = cabeca;
ListNode* segundoNo = cabeca->next;
// Chama recursivamente para o restante da lista e conecta
primeiroNo->next = trocarParesRecursiva(segundoNo->next);
// Troca os dois nós atuais
segundoNo->next = primeiroNo;
// 'segundoNo' se torna a nova cabeça deste par
return segundoNo;
}
Solução Iterativa
Use um ponteiro anterior para conectar os pares trocados. Mantenha o controle dos dois nós a serem trocados e o nó que vem após eles.
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* trocarParesIterativa(ListNode* cabeca) {
// Nó sentinela para facilitar a manipulação da cabeça
ListNode* sentinela = new ListNode(0, cabeca);
ListNode* anterior = sentinela;
while (anterior->next != nullptr && anterior->next->next != nullptr) {
// Define os nós a serem trocados
ListNode* primeiroNo = anterior->next;
ListNode* segundoNo = anterior->next->next;
// Realiza a troca
anterior->next = segundoNo;
primeiroNo->next = segundoNo->next;
segundoNo->next = primeiroNo;
// Move o ponteiro 'anterior' para o próximo par para processar
anterior = primeiroNo; // 'primeiroNo' agora é o segundo nó do par trocado
}
ListNode* resultado = sentinela->next;
// delete sentinela; // Liberar memória
return resultado;
}
- Inverter Nós em Grupos de K
Dada a cabeça de uma lista ligada e um inteiro k, inverta os nós da lista ligada de k em k. Se o número de nós restantes não for um múltiplo de k, deixe-os como estão.
Solução de Simulação com Auxiliar de Inversão
Iteramos pela lista em grupos de k. Para cada grupo, verificamos se há k nós disponíveis. Se houver, invertemos esses k nós e reconectamos a lista. Caso contrário, deixamos o grupo restante como está.
#include <utility> // Para std::pair
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// Função auxiliar para inverter uma sub-lista entre 'inicio' e 'fim' (inclusive)
// Retorna um par: {nova_cabeca, novo_fim} da sub-lista invertida.
std::pair<ListNode*, ListNode*> inverterSubLista(ListNode* inicio, ListNode* fim) {
ListNode* anterior = nullptr;
ListNode* atual = inicio;
ListNode* proximo = nullptr;
ListNode* fimOriginal = fim; // Guarda o fim original para retornar como a nova cabeça
while (atual != fim) {
proximo = atual->next;
atual->next = anterior;
anterior = atual;
atual = proximo;
}
// Agora 'atual' é igual a 'fim'
atual->next = anterior; // Conecta o último nó invertido
return {fim, inicio}; // {novo_fim, nova_cabeca}
}
ListNode* inverterKGroup(ListNode* cabeca, int k) {
if (cabeca == nullptr || k <= 1) {
return cabeca;
}
ListNode* sentinela = new ListNode(0, cabeca);
ListNode* anteriorGrupo = sentinela;
ListNode* atual = cabeca;
while (atual != nullptr) {
ListNode* inicioGrupo = atual;
ListNode* fimGrupo = atual;
// Encontra o k-ésimo nó do grupo
for (int i = 0; i < k - 1; ++i) {
if (fimGrupo == nullptr) {
// Não há nós suficientes para formar um grupo de k
return sentinela->next;
}
fimGrupo = fimGrupo->next;
}
// Se fimGrupo for nullptr, significa que não temos k nós completos
if (fimGrupo == nullptr) {
return sentinela->next;
}
// Salva o nó após o fim do grupo atual para continuar a iteração
ListNode* proximoGrupoInicio = fimGrupo->next;
// Desconecta o grupo atual para poder inverter
fimGrupo->next = nullptr;
// Inverte o grupo atual (inicioGrupo é a cabeça, fimGrupo é a cauda antes de inverter)
std::pair<listnode listnode=""> resultadoInversao = inverterSubLista(inicioGrupo, fimGrupo);
ListNode* novaCabecaGrupo = resultadoInversao.first; // Este era o fim original do grupo
ListNode* novoFimGrupo = resultadoInversao.second; // Este era o início original do grupo
// Reconecta o grupo invertido à lista principal
anteriorGrupo->next = novaCabecaGrupo; // Conecta o nó anterior ao grupo à nova cabeça do grupo
novoFimGrupo->next = proximoGrupoInicio; // Conecta o novo fim do grupo ao início do próximo grupo
// Prepara para o próximo grupo
anteriorGrupo = novoFimGrupo; // O novo fim do grupo atual se torna o anterior para o próximo
atual = proximoGrupoInicio; // Move para o início do próximo grupo
}
return sentinela->next;
}
</listnode>
- Copiar Lista Ligada com Ponteiro Aleatório
Crie uma cópia profunda de uma lista ligada onde cada nó tem um ponteiro adicional random que pode apontar para qualquer nó na lista ou nullptr.
Solução com Intercalação de Nós e Separação
Esta abordagem envolve três passos:
- Intercalar Nós: Para cada nó original
N, crie um novo nó copiadoN'e insira-o imediatamente apósNna lista original. A lista se tornaN1 → N1' → N2 → N2' → ... - Copiar Ponteiros Aleatórios: Para cada nó original
N, seu nó copiadoN'(que éN->next) terá seu ponteirorandomapontando paraN->random->next(seN->randomnão fornullptr). - Separar as Listas: Restaure a lista original separando os nós originais e os nós copiados em duas listas distintas.
// Definição da estrutura do nó da lista ligada com ponteiro aleatório (assumida)
struct Node {
int val;
Node *next;
Node *random;
Node(int x) : val(x), next(nullptr), random(nullptr) {}
};
Node* copiarListaAleatoria(Node* cabeca) {
if (!cabeca) {
return nullptr;
}
// Passo 1: Intercalar os nós copiados após os nós originais
Node* atual = cabeca;
while (atual) {
Node* copiaNo = new Node(atual->val);
copiaNo->next = atual->next;
atual->next = copiaNo;
atual = copiaNo->next; // Avança para o próximo nó original
}
// Passo 2: Copiar os ponteiros aleatórios
atual = cabeca;
while (atual) {
Node* copiaNo = atual->next;
if (atual->random) {
copiaNo->random = atual->random->next; // O ponteiro aleatório do nó copiado aponta para o nó copiado correspondente
} else {
copiaNo->random = nullptr;
}
atual = copiaNo->next; // Avança para o próximo nó original
}
// Passo 3: Separar a lista original e a lista copiada
Node* copiaCabeca = cabeca->next;
Node* atualOriginal = cabeca;
Node* atualCopia = copiaCabeca;
while (atualOriginal) {
atualOriginal->next = atualCopia->next; // Restaura o ponteiro 'next' do nó original
if (atualCopia->next) {
atualCopia->next = atualCopia->next->next; // Define o ponteiro 'next' do nó copiado
}
atualOriginal = atualOriginal->next;
atualCopia = atualCopia->next;
}
return copiaCabeca;
}
- Ordenar Lista Ligada
Ordene uma lista ligada em tempo de execução O(n log n) e em espaço de complexidade constante.
Solução Usando Merge Sort
O Merge Sort é ideal para listas ligadas, pois sua complexidade de tempo é O(n log n) e ele pode ser implementado com espaço constante (O(1)) se feito in-place (ou O(log n) para a pilha de chamadas recursivas).
- Dividir: Encontre o ponto médio da lista ligada usando o algoritmo do ponteiro lento e rápido.
- Conquistar: Recursivamente ordene as duas metades.
- Combinar: Mescle as duas metades ordenadas em uma única lista ordenada.
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// Função auxiliar para mesclar duas listas ligadas ordenadas
ListNode* mesclarDuasListasOrdenadas(ListNode* list1, ListNode* list2) {
ListNode* sentinela = new ListNode(0);
ListNode* ponteiroAtual = sentinela;
while (list1 != nullptr && list2 != nullptr) {
if (list1->val < list2->val) {
ponteiroAtual->next = list1;
list1 = list1->next;
} else {
ponteiroAtual->next = list2;
list2 = list2->next;
}
ponteiroAtual = ponteiroAtual->next;
}
ponteiroAtual->next = (list1 != nullptr) ? list1 : list2;
ListNode* cabecaOrdenada = sentinela->next;
// delete sentinela; // Liberar memória
return cabecaOrdenada;
}
// Função auxiliar para encontrar o nó do meio da lista ligada
ListNode* encontrarMeio(ListNode* cabeca) {
if (!cabeca) return nullptr;
ListNode* lento = cabeca;
ListNode* rapido = cabeca->next; // Começa um passo à frente para retornar o primeiro meio em listas de tamanho par
while (rapido != nullptr && rapido->next != nullptr) {
lento = lento->next;
rapido = rapido->next->next;
}
return lento;
}
ListNode* ordenarLista(ListNode* cabeca) {
// Caso base: lista vazia ou com um único nó já está ordenada
if (cabeca == nullptr || cabeca->next == nullptr) {
return cabeca;
}
// 1. Dividir a lista em duas metades
ListNode* meio = encontrarMeio(cabeca);
ListNode* proximoDoMeio = meio->next;
meio->next = nullptr; // Separa as duas metades
// 2. Ordenar recursivamente as duas metades
ListNode* metadeEsquerdaOrdenada = ordenarLista(cabeca);
ListNode* metadeDireitaOrdenada = ordenarLista(proximoDoMeio);
// 3. Mesclar as duas metades ordenadas
return mesclarDuasListasOrdenadas(metadeEsquerdaOrdenada, metadeDireitaOrdenada);
}
- Mesclar K Listas Ligadas Ordenadas
Mescle k listas ligadas ordenadas em uma única lista ligada ordenada.
Solução Usando Fila de Prioridade (Min-Heap)
Uma abordagem eficiente é usar uma fila de prioridade (min-heap) para manter o menor nó de cada lista ligada. Em cada passo, extraímos o menor nó da fila de prioridade, o adicionamos à lista resultante e inserimos o próximo nó da lista de onde o menor nó foi extraído.
#include <queue>
#include <vector>
// Definição da estrutura do nó da lista ligada (assumida)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// Estrutura para comparação em min-heap
struct Comparador {
bool operator()(ListNode* a, ListNode* b) {
// Queremos um min-heap, então retornamos true se a > b
return a->val > b->val;
}
};
ListNode* mesclarKListas(std::vector<ListNode*>& listas) {
// Cria uma fila de prioridade (min-heap)
std::priority_queue<ListNode*, std::vector<ListNode*>, Comparador> minHeap;
// Insere o primeiro nó de cada lista na fila de prioridade
for (ListNode* lista : listas) {
if (lista != nullptr) {
minHeap.push(lista);
}
}
// Nó sentinela para a lista resultante
ListNode* sentinela = new ListNode(0);
ListNode* ponteiroAtual = sentinela;
// Extrai o menor nó da fila de prioridade e adiciona à lista resultante
while (!minHeap.empty()) {
ListNode* menorNo = minHeap.top();
minHeap.pop();
ponteiroAtual->next = menorNo;
ponteiroAtual = ponteiroAtual->next;
// Se o nó extraído tiver um próximo nó, insira-o na fila de prioridade
if (menorNo->next != nullptr) {
minHeap.push(menorNo->next);
}
}
return sentinela->next;
}
- Cache LRU
Implemente um cache LRU (Least Recently Used) com as operações get e put executando em tempo médio O(1).
Solução com Tabela Hash e Lista Duplamente Ligada
A combinação de uma tabela hash (para acesso O(1) a chaves) e uma lista duplamente ligada (para manter a ordem de uso e permitir inserções/remoções O(1)) é a abordagem padrão para implementar um cache LRU.
- Lista Duplamente Ligada: Mantém os itens em ordem de uso. O nó mais recentemente usado fica no início (após um nó cabeça sentinela), e o menos recentemente usado fica no final (antes de um nó cauda sentinela).
- Tabela Hash: Mapeia a chave do item para seu nó correspondente na lista duplamente ligada, permitindo acesso e atualização rápidos.
#include <unordered_map>
// Estrutura para um nó na lista duplamente ligada
struct DLinkNode {
int key;
int value;
DLinkNode* prev;
DLinkNode* next;
DLinkNode(int k = 0, int v = 0) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
std::unordered_map<int, DLinkNode*> cache; // Mapeia chave para nó
DLinkNode* head; // Nó cabeça sentinela
DLinkNode* tail; // Nó cauda sentinela
int capacity; // Capacidade máxima do cache
int currentSize; // Tamanho atual do cache
// Método privado para remover um nó da lista duplamente ligada
void removeNode(DLinkNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
// Método privado para adicionar um nó ao início da lista (mais recente)
void addToHead(DLinkNode* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
// Método privado para mover um nó existente para o início
void moveToHead(DLinkNode* node) {
removeNode(node);
addToHead(node);
}
// Método privado para remover o nó menos recentemente usado (no final)
DLinkNode* removeTail() {
DLinkNode* res = tail->prev;
removeNode(res);
return res;
}
public:
LRUCache(int capacity) : capacity(capacity), currentSize(0) {
head = new DLinkNode();
tail = new DLinkNode();
head->next = tail;
tail->prev = head;
}
~LRUCache() {
// Limpeza de memória
DLinkNode* current = head->next;
while (current != tail) {
DLinkNode* next = current->next;
delete current;
current = next;
}
delete head;
delete tail;
}
int get(int key) {
if (cache.find(key) == cache.end()) {
return -1; // Chave não encontrada
}
DLinkNode* node = cache[key];
moveToHead(node); // Marca como mais recentemente usado
return node->value;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
// Chave existe: atualiza o valor e move para o início
DLinkNode* node = cache[key];
node->value = value;
moveToHead(node);
} else {
// Chave não existe: cria um novo nó
DLinkNode* newNode = new DLinkNode(key, value);
cache[key] = newNode;
addToHead(newNode);
currentSize++;
// Se exceder a capacidade, remove o item menos recentemente usado
if (currentSize > capacity) {
DLinkNode* tailNode = removeTail();
cache.erase(tailNode->key);
delete tailNode;
currentSize--;
}
}
}
};