I believe this solution would be easier to understand than the current one proposed in Solution1. It does have the same space and time complexity as it is using a new list to hold the sorted elements from both lists.
def merge_list_additional_list(lst1, lst2):
"""
Two pointer solution. We start the head of each list and continue until either one or both lists are exhausted.
Append the rest of the list to the merged list. O(m * n) if any of the list have a different length,
otherwise O(n^2) time and O(n + m) space
:param lst1:
:param lst2:
:return:
"""
i, j = 0, 0
merged_list = []
while i < len(lst1) and j < len(lst2):
if lst1[i] > lst2[j]:
merged_list.append(lst2[j])
j += 1
else:
merged_list.append(lst1[i])
i += 1
if i < len(lst1):
merged_list += lst1[i:]
if j < len(lst2):
merged_list += lst2[j:]
return merged_list