Faça uma função para intercalar listas: a função recebe as duas listas ordenadas e retorna a lista com os elementos das duas listas intercalados conforme a ordem com que elas se dispõe na lista.
Passo 1
O problema pede que a gente crie uma função que recebe duas listas ordenadas e retorna uma lista também ordenada, intercalando elementos das duas listas de entrada.
Passo 2
A ideia é usar dois ponteiros, um para cada lista, percorrendo-as simultaneamente e comparando os elementos atuais. Em cada iteração, adicionamos o menor dos dois elementos à lista resultado e avançamos o ponteiro correspondente.
Passo 3
Quando uma das listas for totalmente percorrida, basta concatenar o restante da outra lista à lista resultado, pois já está ordenado.
Passo 4
Implementamos a função em Python seguindo essa lógica.
Resposta
def intercala(lista1, lista2):
i, j = 0, 0
resultado = []
while i < len(lista1) and j < len(lista2):
if lista1[i] <= lista2[j]:
resultado.append(lista1[i])
i += 1
else:
resultado.append(lista2[j])
j += 1
# Anexa o que sobrou de lista1 ou lista2
resultado.extend(lista1[i:])
resultado.extend(lista2[j:])
return resultado
i, j = 0, 0
resultado = []
while i < len(lista1) and j < len(lista2):
if lista1[i] <= lista2[j]:
resultado.append(lista1[i])
i += 1
else:
resultado.append(lista2[j])
j += 1
# Anexa o que sobrou de lista1 ou lista2
resultado.extend(lista1[i:])
resultado.extend(lista2[j:])
return resultado