BastterCode semana 9 - 21. Merge Two Sorted Lists
comentada em 16/03/2023 09:19

@Giovanni

Faltou atualizar no banner. Ficou bem legal os dois links separados, para o desafio semanal e o mensal.

Demorei um bom tempo pra aprender o que é structure e principalmente pra aprender a mexer nessa que eles fizeram pra definir a linked list.

Essa coisa de precisar usar o operador new para criar espaço na memória e de ter que, a cada novo valor, inicializar o ponteiro para esse novo espaço, descobrir isso me tomou algumas horas frustrantes kkk

Mas é bom que aprendi algo novo, né?

O algoritmo lê cada uma das listas e adiciona os valores armazenados em um vetor, depois usa a função sort para organizar os elementos do vetor em ordem não decrescente e, por último, escreve os valores organizados do vetor em uma nova lista. 

Esses comentários já vieram com o modelo do leetcode. Chuto que o C++ não deve ter uma linked list por padrão e eles precisam criar uma structure para definir uma lista dessas.

Depois eu vejo se descubro alguma forma mais eficiente de fazer.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* list3 = new ListNode();
        ListNode* ans = nullptr;
        vector<int> num;
        
        while (list1) {
            num.push_back(list1->val);
            list1 = list1->next;
        }
        
        while (list2) {
            num.push_back(list2->val);
            list2 = list2->next;
        }
        
        if (num.size() == 0) {
            return ans;
        }
        
        sort(num.begin(), num.end());
        ans = list3;
        
        for (int i = 0; i < num.size(); i++) {           
            list3->val = num[i];
            
            if (i+1 < num.size()) {
                list3->next = new ListNode();
                list3 = list3->next;
            }
        }
        
        return ans;
        
    }
};?

Uma versão quase igual, mas usando map em vez de vector. Como as chaves do map já são ordenadas da menor para a maior, não precisa fazer uma ordenação extra como no caso do vector.

Aproveitei e coloquei os valores do map como char, já que o intervalo de valores para o problema é muito pequeno e não é preciso usar um tipo mais custoso como o int (não que faça grande diferença no fim das contas kkk).

O desempenho foi melhor, mas eu mandei várias vezes ambas as soluções e deu aquelas variações enormes que sempre dá. Então no fim das contas não dá pra saber nada sobre o desempenho kkk.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* list3 = nullptr;
        ListNode* ans = nullptr;
        map<char,char> num;
        
        while (list1) {
            num[list1->val]++;
            list1 = list1->next;
        }
        
        while (list2) {
            num[list2->val]++;
            list2 = list2->next;
        }
        
        if (num.size() == 0) {
            return ans;
        }
        
        list3 = new ListNode();        
        ans = list3;
        
        for (::map<char,char>::iterator it = num.begin(); it != num.end(); it++) {
            for(char repeat = it->second; repeat > 0; repeat--) {
                list3->val = it->first;
            
                if (distance(it, num.end()) > 1 || repeat > 1) {
                    list3->next = new ListNode();
                    list3 = list3->next;
                }
            } 
        }
        
        return ans;
        
    }
};?

@gustavo poderia ver o link do semanal no banner por favor?

@oxe

a VM que eles disponibilizam tem bastante variação mesmo
conforme os desafios ficam mais complexos, parece que a variação é maior ainda

uma alternativa é pensar na complexidade da solução usando big O notation que é agnóstico ao sistema/plataforma que roda

Big O notation - Wikipedia

Solução em C++

Processador O(n)
Memória O(1)

class Solution {
public:
    
    ListNode* takeLowest(ListNode** list1, ListNode** list2) {
        ListNode* header = nullptr;
        if ((*list1)->val <= (*list2)->val) {
            header = *list1;
            *list1 = (*list1)->next;
        } else {
            header = *list2;
            *list2 = (*list2)->next;
        }
        return header;
    }
    
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* header = nullptr;
        ListNode* sol = nullptr;
        
        
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;

        header = takeLowest(&list1, &list2);
        
        sol = header;
        
        while(list1 != nullptr || list2 != nullptr) {
            if (list1 != nullptr && list2 != nullptr) {               
                 header->next = takeLowest(&list1, &list2);
            }
            else if (list1 != nullptr) {
                header->next = list1;
                list1 = list1->next;
            } else {
                header->next = list2;
                list2 = list2->next;
            }
            
            header = header->next;
            
        }
        
        
        
        return sol;
    }
};?

Muito legal, cara. 

Ainda me falta esse tino de separar cada tarefa em sua respectiva função. 

Outra coisa que eu sempre fico na dúvida é se é melhor usar as funções das libraries ou fazer a própria função. Parece um trade-off entre conveniência, de um lado, e controle do que tá acontecendo, de outro. 

postado por @FlyCavok em 08/03/2023 12:41

Solução em C++

Processador O(n)
Memória O(1)

class Solution {
public:
    
    ListNode* takeLowest(ListNode** list1, ListNode** list2) {
        ListNode* header = nullptr;
        if ((*list1)->val <= (*list2)->val) {
            header = *list1;
            *list1 = (*list1)->next;
        } else {
            header = *list2;
            *list2 = (*list2)->next;
        }
        return header;
    }
    
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* header = nullptr;
        ListNode* sol = nullptr;
        
        
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;

        header = takeLowest(&amp;list1, &amp;list2);
        
        sol = header;
        
        while(list1 != nullptr || list2 != nullptr) {
            if (list1 != nullptr &amp;&amp; list2 != nullptr) {               
                 header->next = takeLowest(&amp;list1, &amp;list2);
            }
            else if (list1 != nullptr) {
                header->next = list1;
                list1 = list1->next;
            } else {
                header->next = list2;
                list2 = list2->next;
            }
            
            header = header->next;
            
        }
        
        
        
        return sol;
    }
};?class Solution {

@oxe Sempre que possível use as funções das libs.

No leetcode você deve implementar na mão, mas é pq é para aprender. No dia a dia é para usar da lib sim. O código da lib é quase sempre melhor que o seu, é mais testado e é mantido funcionando por outras pessoas.

O maior desafio de quem desenvolve não é criar, é manter. Criar é fácil. Manter é foda. Quanto menos código tiver vindo de você, mais fácil será manter.

Porém no contexto do estudo é diferente. Não adianta nada vc pegar um exercício que ensina sobre filas  (Queue / FIFO) e usar um método pré-pronto.

Ou um exercício mandando ordenar um array na mão e o cara responder com .sort().  Isso não é aprender a programar! Qualquer um gasta menos de 1 minuto pra pegar o método que faz sort do array.

O correto é implementar na unha, na fase de aprendizado. 

@FlyCavok

Muito legal, obrigado pela lição. Você tá totalmente certo, tudo que eu fiz na mão eu aprendi muito no processo.

Vou fazer isso a partir do próximo desafio, tentar fazer tudo desde a base! 

Não precisa ser tudo na mão.

Por ex, a questão quer uma pilha pra resolver,vc usa a pilha que existe na lib. A questão é para implementar uma pilha, vc implementa sem usar nenhum recurso da lib!

Dessa vez eu apanhei bastante

class LinkedList:
    def __init__(self):
        self.head = None

    def __repr__(self):
        return f'LinkedList(head={self.head})'

    def append(self, value):
        new_node = ListNode(value)

        if self.head is None:
            self.head = new_node
            return

        last_node = self.head
        while last_node.next:
            last_node = last_node.next

        last_node.next = new_node
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode],
                      list2: Optional[ListNode]) -> Optional[ListNode]:
        if not (list1 and list2):
            return list1 or list2

        result = LinkedList()

        while list1 and list2:
            if list1.val <= list2.val:
                result.append(list1.val)
                list1 = list1.next
            else:
                result.append(list2.val)
                list2 = list2.next

        while list1:
            result.append(list1.val)
            list1 = list1.next
        
        while list2:
            result.append(list2.val)
            list2 = list2.next

        return result.head

Ver mais

Oxe e/ou FlyCavok: olhando a solução de vocês, fiquei com uma dúvida... Pelo o que entendi (tenho zero C++), vocês tem uma variável ans (Oxe) e sol (Flycavok) que vai ser a resposta, mas no laço vocês só mexem no list3 (Oxe) ou header (FlyCavok)... Que bruxaria é essa? kkk Quando colocam ans = list3 ou sol = header estes dois objetos apontam para o mesmo lugar na memória, então quando atualizam um, atualizam o outro?

Pergunto porque queria entender se poderia ter feito algo similar em Python, sem precisar criar uma outra classe como eu fiz, e usar apenas a ListNode que o Leetcode já fornece...

ps.: Se for levar mais que 5 minutos do tempo de vocês para explicar, deixa quieto, kkk É só uma curiosidade mesmo

pps.: Eu me lembro do exemplo de Python que o pessoal costuma ensinar, onde um objeto é uma cópia de outro, e ao mudar na cópia, mudamos no original... Mas não consegui ver como usar isso no meu caso

>>> a = [0, 1]
>>> b = a  # b copy a
>>> b[0] = 'a'  # change b
>>> print(a, b)  # a also changed...
['a', 1] ['a', 1]

@PMHM

É isso mesmo. São ponteiros, que apontam para um lugar na memória.

Eles não "armazenam" valores, então quando você mexe nos valores do espaço da memória apontado pelo ponteiro, ele passa a referenciar esses novos valores (porque o espaço na memória é o mesmo, só que agora os valores desse espaço são diferentes). 

É preciso ter dois ponteiros porque um dos ponteiros vai mudar, passar a indicar outro espaço na memória. No meu caso, o list3 vai mudando no último for para apontar para cada nó da linked list e, assim, poder preencher esse nó com o número que deve ficar nele.

Isso significa que list3 passa a apontar apenas para o "rabo" da linked list, enquanto o ans aponta para a posição inicial de list3, ou seja, para a "cabeça" com todo o resto atrás.

A complicação da linked list é que os valores são amarrados aos ponteiros e você precisa criar espaço na memória e movimentar o ponteiro manualmente.

É diferente de um vetor ou um array, por exemplo, que faz tudo isso automaticamente, por "baixo dos panos", quando você insere os valores. O vetor ou o array permitem que você trabalhe num nível de abstração mais elevado. 

Aí foi isso que eu demorei pra entender. Tive que internalizar que no final das contas era apenas um array de inteiros mais complicado de se usar.

Só não sei ainda quando faz sentido usar uma linked list dessas no lugar de um vetor ou um array. Talvez seja o que o FlyCavok disse, é algo que você faz manualmente pra aprender e depois não usa mais na prática, não sei. 

Boa, @oxe ! Deu pra entender bem a questão dos dois ponteiros... Eu estava justamente com dificuldade de entender porque eram necessários dois deles, mas agora ficou claro: um fica ancorado na primeira posição da resposta, e o outro vai percorrendo a resposta, e mudando ela in situ. Eu acho que daria para ter feito algo análogo então, na minha solução...

Obrigado!

Se eu tiver um tempo, vou tentar refatorar meu código para deixá-lo mais simples

@PMHM

Esse vídeo aqui é bem legal e explica as diferenças entre array e linked list.

postado por @PMHM em 08/03/2023 21:10

Oxe e/ou FlyCavok: olhando a solução de vocês, fiquei com uma dúvida... Pelo o que entendi (tenho zero C++), vocês tem uma variável ans (Oxe) e sol (Flycavok) que vai ser a resposta, mas no laço vocês só mexem no list3 (Oxe) ou header (FlyCavok)... Que bruxaria é essa? kkk Quando colocam ans = list3 ou sol = header estes dois objetos apontam para o mesmo lugar na memória, então quando atualizam um, atualizam o outro?

Pergunto porque queria entender se poderia ter feito algo similar em Python, sem precisar criar uma outra classe como eu fiz, e usar apenas a ListNode que o Leetcode já fornece...

ps.: Se for levar mais que 5 minutos do tempo de vocês para explicar, deixa quieto, kkk É só uma curiosidade mesmo

pps.: Eu me lembro do exemplo de Python que o pessoal costuma ensinar, onde um objeto é uma cópia de outro, e ao mudar na cópia, mudamos no original... Mas não consegui ver como usar isso no meu caso

>>> a = [0, 1]
>>> b = a  # b copy a
>>> b[0] = 'a'  # change b
>>> print(a, b)  # a also changed...
['a', 1] ['a', 1]

Isso que você demonstrou não é uma cópia, mas variáveis diferentes que apontam para o mesmo objeto.

Por isso que quando você altera uma das variáveis, a outra vai demonstrar a alteração, pois ambas estão referenciando o mesmo objeto (que foi modificado).

Uma cópia (que inicialmente possui os mesmos dados do original) deve apontar para outro objeto, a fim de que as alterações feitas em um não afetem o outro (e vice-versa).

Ex:

>>> a = [0, 1]
>>> b = a
>>> c = a.copy()
>>> b[0] = 'a'
>>> print(a, b, c)
['a', 1] ['a', 1] [0, 1]

>>> id(a) == id(b)
True    => Ou seja, a e b apontam para o mesmo objeto na memória
>>> c[0] = 'a'
>>> id(a) == id(c)
False => Ainda que tenha alterado a variável c para ficar com dados iguais da variável a, não se tratam do mesmo objeto (possuem apenas as mesmas informações, mas ocupam locais distintos na memória).

OBS: Outra opção para copiar um obeto (do tipo lista) é "fatiá-lo" do início ao fim:
>>> d = a[:]
>>> print(a, d)
['a', 1] ['a', 1]
>>> id(a) == id(d)
False

@PMHM

Isso. Toda vez que você atribui um endereço a um ponteiro e mexe nele, perde o endereço

Endereço de memória é um número. Se você mexer nele, perde. Então no meu código eu salvo ele aqui:

sol = header;?

E assim posso detonar a variável header à vontade....

E lá no fim, eu retorno:

return sol;?

LinkedList é um tipo de estrutura muito usada como base para Queue e Stack.

Em uma Queue (ou fila), você quer sempre colocar o dado ao final dela e sempre acessar o dado do começo. Então a LinkedList permite que você adicione infinitos elementos em tempo O(1) de execução, isto é, máxima eficiência, e também que remova em tempo O(1).

Em Stack também, só que você quer sempre colocar ao final da lista e remover do final também.

Queue = FIFO = First-in first-out
Stack = LIFO = Last-in first-out
LinkedLists são péssimas em acessar dados aleatórios. Se você quer acessar o dado na posição 10, você precisa começar da posição 0, ir até a 1, depois 2, depois 3.... até chegar lá.

Porém para inserir/remover do começo (head) ou do final (tail) são ótimos. E podem crescer para ambas as direções continuamente.

Por isso elas são muito usadas como base de implementação de Stack e Queue.

Valeu Oxe, FlyCavok e shadow_walker!

Perdi a última semana mas vamos lá, Java:

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
        ListNode head = null;
        ListNode tail = null;
        while(list1 != null || list2 != null){
            ListNode toAdd = null;
            if(list2 == null || (list1 != null && list1.val < list2.val)){
                toAdd = list1;
                list1 = list1.next;
            }else{
                toAdd = list2;
                list2 = list2.next;
            }
            if(head == null){
                head = toAdd;
                tail = toAdd;
            }else{
                tail.next = toAdd;
                tail = toAdd;
            }
        }

        return head;
    }

}       ?

Solução em Elixir, usando recursão pra montar a nova lista

defmodule Solution do
  @spec merge_two_lists(l1 :: ListNode.t() | nil, l2 :: ListNode.t() | nil) :: ListNode.t() | nil
  def merge_two_lists(l1, l2) do
    case {l1, l2} do
      {nil, nil} -> nil
      {%ListNode{}, nil} -> %{l1 | next: merge_two_lists(l1.next, nil)}
      {nil, %ListNode{}} -> %{l2 | next: merge_two_lists(nil, l2.next)}
      {%ListNode{}, %ListNode{}} when l1.val < l2.val -> %{l1 | next: merge_two_lists(l1.next, l2)}
      {%ListNode{}, %ListNode{}} -> %{l2 | next: merge_two_lists(l1, l2.next)}
    end
  end
end

@lucaspaszinski5770   Legal cara, bem diferente.

o que isso faz? {nil, nil} -> {nil} ?

@FlyCavok

Pelo que entendi, ele monta uma lista a partir das duas listas. O primeiro elemento nas chaves é da l1 e o segundo da l2. Nessa chave aí, tem dizendo que se o valor em l1 e l2 é NULL, o da lista montada será NULL também. Ou seja, chegou ao final.

Aí depois ele vai cuidar dos demais casos. Se ainda tem valor em l1, mas l2 chegou ao NULL, ele pega o valor de l1 e chama a função recursivamente para o próximo nó de l1. O mesmo se l1 é NULL e l2 tem valor. Se ambos, l1 e l2, ainda tiverem valor, ele vê qual é menor e pega, chamando a função recursivamente com incremento da lista que tinha o menor valor.

Eu só não entendi quando a função termina.