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.