educative.io

Educative

An alternative to Solution 1 for Merge Two Sorted Lists

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
1 Like

Thank you @Dragos1. This is a good solution.
Anum Hassan|Developer Advocate
educative.io

In this course section on merging two sorted lists. Isn’t this just as a efficient

def mergeList(list1, list2):
    n1,n2 = len(list1), len(list2)
    if n2> n1:
        list2.extend(list1) # O(n1)
        list2.sort() # O((n1 + n2) Log (n1 + n2))  = O(n Log n)
        return list2
    else:
        list1.extend(list2) # O(n2)
        list1.sort() # O((n1 + n2) Log (n1 + n2)) = O(n Log n)
        return list1

Which if n1 == n2 == n we have as O(n)

2 Likes

Wow, that’s great @Oti_Rowland.
Happy Learning at Educative :slight_smile:
Anum Hassan|Developer Advocate
Educative.io

1 Like

@Dragos1 nice solution. You can also remove the last two if statements by adding one extra condition in the first if statement.

def merge_lists(lst1, lst2):
   i, j = 0, 0
   result = []
   while i < len(lst1) and j < len(lst2) :
       if i < len(lst1) and lst1[i] < lst2[j]:
           result.append(lst1[i])
           i += 1
       else:
           result.append(lst2[j])
           j += 1
   return result

@Anum_Hassan

What about this?

    def merge_lists(lst1, lst2):
           lst1.extend(lst2)
           lst1.sort()
           return lst1

Does this valid?
def merge_lists(lst1,lst2):
return sorted(lst1+lst2)