Mesclar duas listas encadeadas ordenadas

Mescle duas listas encadeadas ordenadas e retorne uma nova lista encadeada ordenada. A nova lista encadeada deve ser formada unindo os nós de duas listas encadeadas.

Entrada

A classe dos nós da lista simplesmente encadeada é definida na aba Testes. As listas encadeadas são criadas a partir dos dados de listas comuns e fornecidas à função. Cada nó contém um valor e a referência para o próximo nó.

class ListNode:
    def __init__(self, val=0, next_element=None):
        self.val = val
        self.next_element = next_element

Saída

Retorne a referência para o primeiro nó da sequência de dados não vazia. Se uma das listas encadeadas for None, retorne a referência para a outra. Se ambas as listas encadeadas forem None, retorne None. Se ambas as listas encadeadas tiverem dados, organize as referências de modo que uma nova lista encadeada ordenada seja formada.

Exemplos

a1 = [1, 2, 4]
a2 = [1, 3, 4]
lst1 = ListNode(a1[0]) if a1 else None
if a1 and len(a1) > 1:
    lst1.add_data(a1[1:])
lst2 = ListNode(a2[0]) if a2 else None
if a2 and len(a2) > 1:
    lst2.add_data(a2[1:])
merged_lst = merge_two_lists(lst1, lst2)
print(merged_lst.all_nodes_data() if merged_lst else []) ➞ [1, 1, 2, 3, 4, 4]

b1 = [13, 69]
b2 = []
lst1 = ListNode(b1[0]) if b1 else None
if b1 and len(b1) > 1:
    lst1.add_data(b1[1:])
lst2 = ListNode(b2[0]) if b2 else None
if b2 and len(b2) > 1:
    lst2.add_data(b2[1:])
merged_lst = merge_two_lists(lst1, lst2)
print(merged_lst.all_nodes_data() if merged_lst else []) ➞ [13, 69]

lst1 = None
lst2 = None
merged_lst = merge_two_lists(lst1, lst2)
print(merged_lst.all_nodes_data() if merged_lst else []) ➞ []

Observações

Tente evitar criar novos nós e copiar valores (concentre-se em reorganizar self.next_element).