_Créditos das imagens: ChatGPT
**Título:** LeetCode 23: Mesclando K Listas Ordenadas com Harbour/xBase e Reutilização de Código
**Introdução**
Olá, entusiastas de Harbour/xBase e desafios de programação! Depois de explorarmos como mesclar duas listas ordenadas no [nosso post sobre o LeetCode 21](https://www.blacktdn.com.br/2025/03/blacktdn-leetcode-21-merge-two-sorted.html), vamos dar um passo adiante e enfrentar um problema um pouco mais complexo: o LeetCode 23 - Merge K Sorted Lists.
Neste artigo, vamos desvendar uma implementação em Harbour/xBase para este desafio, demonstrando como podemos inteligentemente reutilizar a solução que já construímos para o problema 21. Veremos como a modularidade e a construção sobre soluções anteriores podem simplificar problemas mais complexos.
**O Problema: LeetCode 23 - Merge K Sorted Lists**
O desafio é o seguinte: dado um array (`aLists` em nossa implementação) contendo `k` listas encadeadas, onde cada lista já está ordenada em ordem crescente, precisamos mesclar todas essas `k` listas em uma única lista encadeada, também ordenada de forma crescente.
* **Entrada:** Um array de ponteiros/objetos, onde cada elemento aponta para o nó inicial (head) de uma lista encadeada ordenada.
* **Saída:** O nó inicial (head) da nova lista encadeada única, contendo todos os elementos das listas originais, em ordem crescente.
**Exemplo:**
Se a entrada for `[[1,4,5],[1,3,4],[2,6]]`, a saída esperada é `[1,1,2,3,4,4,5,6]`.
**A Abordagem em Harbour/xBase: Mesclagem Iterativa**
Como podemos resolver isso em Harbour/xBase? Uma abordagem bastante intuitiva, especialmente considerando que já temos uma função para mesclar *duas* listas (`MergeTwoLists`, do problema 21), é aplicar essa função repetidamente.
A estratégia é a seguinte:
1. **Inicialização:** Começamos com a primeira lista (`aLists[1]`) como nossa lista "mesclada" inicial.
2. **Iteração:** Percorremos o restante das listas no array de entrada (da segunda até a k-ésima).
3. **Mesclagem:** Em cada passo, pegamos a lista "mesclada" atual e a mesclamos com a próxima lista do array de entrada (`aLists[nI]`), usando nossa função `MergeTwoLists`.
4. **Atualização:** O resultado dessa mesclagem se torna a nova lista "mesclada".
5. **Resultado:** Após iterar por todas as listas, a lista "mesclada" final conterá todos os elementos de todas as listas originais, devidamente ordenados.
Tratamos também alguns casos base:
* Se o array de entrada estiver vazio, retornamos `NIL`.
* Se o array de entrada contiver apenas uma lista, simplesmente retornamos essa lista.
**Análise do Código (`merge_k_sorted_lists.23.1.prg`)**
Vamos dar uma olhada na implementação em Harbour/xBase que segue essa abordagem:
```prg
/*
* LeetCode 23: Merge k Sorted Lists
* Author: naldodj (naldo.dj@gmail.com)
* Link: https://leetcode.com/problems/merge-k-sorted-lists/
* Date: 2024-07-28
* Language: Harbour (xBase)
*
* Definition for singly-linked list. (Assumed structure)
* CLASS TListNode
* DATA value
* DATA next INIT NIL
* ENDCLASS
*
*/
#include "hbclass.ch" // Required for CLASS syntax if not default
FUNCTION MergeKLists( aLists )
LOCAL nI
LOCAL aMergedList
// Caso base: Array vazio
IF EMPTY( aLists )
RETURN {}
ENDIF
// Caso base: Apenas uma lista no array
IF LEN( aLists ) == 1
RETURN aLists[ 1 ]
ENDIF
// Inicializa a lista mesclada com a primeira lista
aMergedList := aLists[ 1 ]
// Itera a partir da segunda lista
FOR nI := 2 TO LEN( aLists )
// Reutiliza a função MergeSortedLists para mesclar a lista atual
// com a próxima lista do array.
aMergedList := MergeSortedLists( aMergedList, aLists[ nI ] )
NEXT
// Retorna a lista final mesclada e ordenada
RETURN aMergedList
/*
* NOTE: This function depends on the MergeTwoLists function,
* likely defined elsewhere (e.g., in the solution for LeetCode 21).
*
* FUNCTION MergeTwoLists( list1, list2 )
* // ... implementation to merge two sorted lists ...
* END FUNCTION
*/
// -- Assume TListNode CLASS definition is available --
// CLASS TListNode
// ...
// ENDCLASS
```
**Pontos Chave da Implementação:**
1. **Função `MergeKLists( aLists )`:** Recebe o array `aLists` contendo os nós iniciais das `k` listas.
2. **Tratamento de Casos Base:** Verifica se `aLists` está vazio ou contém apenas uma lista.
3. **Inicialização:** `aMergedList := aLists[ 1 ]` pega a primeira lista como ponto de partida.
4. **Loop `FOR nI := 2 TO LEN( aLists )`:** Itera pelas listas restantes.
5. **Reutilização Crucial:** `aMergedList := MergeSortedLists( aMergedList, aLists[ nI ] )`. Aqui está a mágica! A cada iteração, chamamos a função `MergeSortedLists` (que resolve o LeetCode 21) para combinar o resultado acumulado (`aMergedList`) com a próxima lista (`aLists[ nI ]`).
6. **Retorno:** `RETURN aMergedList` devolve o nó inicial da lista completamente mesclada.
**A Beleza da Reutilização: Conectando com LeetCode 21**
A elegância desta solução reside na sua simplicidade e na forma como ela constrói sobre um problema já resolvido. Ao invés de reinventar a roda para mesclar `k` listas de uma vez (o que poderia envolver estruturas de dados mais complexas como heaps), ela decompõe o problema: mesclar `k` listas é simplesmente mesclar duas listas, `k-1` vezes.
Isso destaca a importância de ter funções bem definidas e reutilizáveis. A nossa solução para o LeetCode 21 (`MergeTwoLists`) torna-se um bloco de construção fundamental para resolver o LeetCode 23.
Você pode encontrar a implementação da função `MergeTwoLists` referenciada aqui:
* [naldodj/naldodj-xbase-leetcode-solutions/src/hb/021/merge_two_sorted_lists.21.1.prg](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/hb/021/merge_two_sorted_lists.21.1.prg)
E a implementação completa que acabamos de analisar para o LeetCode 23:
* [naldodj/naldodj-xbase-leetcode-solutions/src/hb/023/merge_k_sorted_lists.23.1.prg](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/hb/023/merge_k_sorted_lists.23.1.prg)
**Conclusão**
Resolver o LeetCode 23 em Harbour/xBase usando uma abordagem iterativa que reutiliza a solução do LeetCode 21 é uma demonstração prática de como simplificar problemas complexos. Embora possam existir abordagens com melhor desempenho teórico para um número muito grande de listas (como "dividir para conquistar" ou usar um min-heap), esta solução é clara, fácil de entender e implementar, e muito eficiente na prática para muitos cenários.
Ela também serve como um ótimo exemplo do poder da reutilização de código no desenvolvimento de software, um princípio fundamental que transcende linguagens e plataformas.
Espero que esta análise tenha sido útil! Continue praticando e explorando o mundo dos algoritmos com Harbour/xBase.
**Links Úteis:**
* **LeetCode Problema 23:** [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)
* **Solução Harbour (LeetCode 23):** [merge_k_sorted_lists.23.1.prg no GitHub](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/hb/023/merge_k_sorted_lists.23.1.prg)
* **Solução Harbour (LeetCode 21):** [merge_two_sorted_lists.21.1.prg no GitHub](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/hb/021/merge_two_sorted_lists.21.1.prg)
* **Post Relacionado (LeetCode 21):** [BlackTDN LeetCode 21: Mesclando Duas Listas Ordenadas em Harbour/xBase](https://www.blacktdn.com.br/2025/03/blacktdn-leetcode-21-merge-two-sorted.html)
**HashTags:**
#xBase, #LeetCode, #LeetCode23, #merge_k_sorted_lists, #Algoritmo, #ReaproveitamentoDeCodigo
Até a próxima!
---
Comentários
Postar um comentário