Merge Two Sorted List - LeetCode

📝 Descrição

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

📌 Exemplos

Exemplo 1

Entrada

list1 = [1,2,4], list2 = [1,3,4]

Saída

[1,1,2,3,4,4]

✅ Casos de teste

Caso 1

Entrada

list1 = [], list2 = []

Saída

[]

🚀 Como resolvi?

Pô, te falar que lidar com lista é meio chato. Sempre precisamos aplicar algumas guardrails que não faríamos com vetores.

Vamos pensar um pouco sobre o problema. Dado duas listas ordenadas gostaríamos de ter a terceira lista que é a junção das duas fornecidas.

1. Para que preservemos a ordenação das listas, temos de comparar o atual elemento da list1 com o da list2 e ver qual deles é o atual da lista unificada.
2. As listas podem ser de tamanhos diferentes. Caso uma seja totalmente processada, precisamos apontar para o restante da que sobrou.
3. Temos de usar um dummy para não perder referência da cabeça da lista.

Além disso, sempre que estiver lidando com lista, é interessante saber os padrões para a resolução do problema. Por exemplo

Navegando em uma lista ligada

curr = l1
while curr:
	curr = curr.next

Proteção da Head

dummy = ListNode(0, head)
curr = dummy

Apontar para o próximo nó

curr.next = l1

🛠️ Implementação

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
	dummy = ListNode()
	curr = dummy
 
	while list1 and list2:
		if list1.val < list2.val:
			curr.next = list1
			list1 = list1.next
		else:
			curr.next = list2
			list2 = list2.next
		curr = curr.next
 
	curr.next = list1 if list1 else list2
 
	return dummy.next