Tag: merge sorted list

This post explains how to solve leetcode problem – 21. merge two sorted list – using python 3. Let’s take a look at an example. Let’s say there are two lists: 1 -> 3 -> 5 and 2 -> 4. After merging those lists, the expected answer is 1 -> 2 -> 3 -> 4 -> 5. You are supposed to merge the list in sorted order. This problem doesn’t require any tricks but you just need to be able to operate on iterating and merging the list. With that said, the algorithm is very simple.
1. iterate nodes in each list at the same time until at least one list is completely consumed
2. push the smaller node to the result list (merged)
3. After #1, 2, if there is any left over from either of the list, just append to the result list

Let’s take a look at working solution here. In the solution below, I used a dummy node so that I can blindly set the next pointer without having to worry about if it’s first node or not. You just need to make sure not to return the dummy node.

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    merged = ListNode(-1)
    iter = merged
    while list1 and list2:
        if list1.val < list2.val:
            iter.next = list1
            list1 = list1.next
        else:
            iter.next = list2
            list2 = list2.next
        iter = iter.next

    if list1:
        iter.next = list1
    elif list2:
        iter.next = list2

    return merged.next

As you see in the solution above, I am iterating the two lists at the same time, setting the smaller value node to the result list. Once at least one list is completely consumed, I need to check if there are any leftovers and append them to the result.

Time complexity is O(n + m) where n is the length of list1 and m is the length of list2. Space complexity is O(1) since I don’t need any extra space.