The Blind 75 Leetcode Series: Merge Two Sorted Lists

7 min readApr 13, 2022

Today, we will be working on Merge Two Sorted Lists.

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

As usual, we want to make the problem description more complete.

is it possible to have empty linked list for either or both?
is there a range for the value for each node?
The example shows ascending order. Do we assume that’s always the case?

If the answers are “yes”, “within -2³¹ to 2³¹-1”, and “yes, always ascending”, then the question becomes

You are given the heads of two sorted linked lists list1 and list2. Both could be empty.
The values are within -2³¹ to 2³¹-1
Merge the two lists in a one sorted list, ascending. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

The values probably won’t matter since we are comparing 2 values, but if we are storing the values for some reason, we want to make sure the variable can actually store the values.

Let’s get to it.

The most important fact here is that both lists are sorted in ascending way, so we know for sure the values go from lowest to highest. We just don’t know which list has lower value for the current node, so we need to compare them. As we choose the node as the next node to our merged list, we move to the next node of that list. For example, if the node for list1 has 2 as the value and 3 for list2, our merged list would choose the node in list1 as the next node, then we want to move onto list1’s next node. Going back to the visual example, once we compare the 2 and the 3 , we choose list1’s 2 as the node, then we move the pointer for list1 onto the next node, which is the node with value 4.

When two nodes have the same value, we don’t care which one goes in first, so we can arbitrarily choose one as long as we move the pointer of the correct list.

Eventually we will reach the end of one list, which has the pointer pointing to null. At the point, we still need to make sure the other list (or what’s left of it) is linked to the merged list.

Therefore, the algorithm becomes

def mergeTwoLists(list1, list2):
    head = ListNode()  # this is the merged list, or the first node of the list. Or dummy node
    begin = head  # we want to have a pointer pointing to the beginning since the "head" will keep moving
    # when both lists are present, compare the values, choose the lower one to link to the merged list, move the pointer of that list, then move the head
    while list1 and list2:
        if list1.val <= list2.val:
            head.next = list1
            list1 = list1.next
        else:
            head.next = list2
            list2 = list2.next
        head = head.next
    # when one list runs out, check which list still has nodes left, directly link the rest to the merged list
    if list1:
        head.next = list1
    if list2:
        head.next = list2
    # since we link the first node to head.next, we return begin.next
    return begin.next

For the time complexity

def mergeTwoLists(list1, list2):
    head = ListNode()
    begin = head
    
    while list1 and list2:  # O(N1 + N2)
        if list1.val <= list2.val:
            head.next = list1
            list1 = list1.next
        else:
            head.next = list2
            list2 = list2.next
        head = head.next
    
    if list1:  # O(1)
        head.next = list1
    if list2:  # O(1)
        head.next = list2
    
    return begin.next

So we are looking at O(N1+N2), where N1 is the length of list1 and N2 is the length of list2. Time will be shorter if the shorter list has lower value, potentially making the best case O(N1) and N1 < N2.

Of course, this is not the only way to solve this problem. We solved the problem iteratively, using a while loop to check for the conditions of the two lists. We can also use a recursive way to solve the problem by repeatedly calling the function itself and pass in different inputs.

Recursion requires a base condition check so we know when we stop doing recursion. For this problem, the base condition is when one of the list reaches the end (null). We know that we need to return the rest of the other list if we find one list empty. The base condition would be

if not list1 or not list2:  # if either list is empty
    return list1 or list2  # return the one that has node

Next, we need to know what we pass in as args and what we expect out of the function as output. Since our base condition returns “the rest of one list”, we know that we need to attach that to a node, much like how we do in previous solution head.next = l2 for example. Now we have

head.next = mergeTwoListRecursive(list1, list2)

Then we still need to compare the two values to know which list to take, so if list1.val <= list2.val: still needs to be checked. For the iterative approach, we have the following lines inside the if-block

head.next = list1
list1 = list1.next
head = head.next # this is outside of the if-else block, but it's executed every time in the while block ,so I counted it in

But then the recursive function only takes list1 and list2 , so we need to find a way to combine the first two lines above.

The output of the recursive function is a node, so intuitively we would think of using some_node.next = mergeTwoListRecursive(list1, list2) , but what’s the some_node if we can’t use head? list1 or list2?

Using a short example, we can illustrate this easily. Imagine we only have list1=[1] and list2=[2], so entering the if-block, list1 will be taken, and we need to append list2 to it, so we should use list1.next = mergeTwoListRecursive(...) , but now we’ve chosen a node out of list1 already, so we need to move the pointer and have list1 = list1.next. To do that, we simply need to pass in list1.next into the function and we have effectively taken out the node chosen.

Same idea when list2 has smaller value. We take the node from list2, call the recursive function on list1, and list2.next.

The algorithm becomes

def mergeTwoListRecursive(list1, list2):
    # base condition   
    if not list1 or not list2:  # if either list is empty
        return list1 or list2  # return the one that has node
    # compare values
    if list1.val <= list2.val:
        list1.next = mergeTwoListRecursive(list1.next, list2)
    else:
        list2.next = mergeTwoListRecursive(list1, list2.next)

What are we missing? We still need to return something in the if-else block, otherwise mergeTwoListRecursive(list1.next, list2) will return null if it’s not fitting the base condition. If list1.val ≤ list2.val, we modify the .next for list1, so it makes sense to return list1 in that block. The same idea applies to else block. Finally, we have

def mergeTwoListRecursive(list1, list2):
    # base condition   
    if not list1 or not list2:  # if either list is empty
        return list1 or list2  # return the one that has node
    # compare values
    if list1.val <= list2.val:
        list1.next = mergeTwoListRecursive(list1.next, list2)
        return list1    else:
        list2.next = mergeTwoListRecursive(list1, list2.next)
        return list2

We still need to apply our first node (or dummy node), and we can initiate that in another function which calls our mergeTwoListRecursive.

def mergeTwoListRecursive(list1, list2):
    # base condition   
    if not list1 or not list2:  # if either list is empty
        return list1 or list2  # return the one that has node
    # compare values
    if list1.val <= list2.val:
        list1.next = mergeTwoListRecursive(list1.next, list2)
        return list1    else:
        list2.next = mergeTwoListRecursive(list1, list2.next)
        return list2def mergeTwoLists(list1, list2):
    head = ListNode()
    begin = head
    head.next = mergeTwoListRecursive(list1, list2)
    return begin.next

And that is really it! We’ve solved this problem using recursion! Last, let’s check the time complexity one more time

def mergeTwoListRecursive(list1, list2):
    if not list1 or not list2:  # O(1)
        return list1 or list2  
    # each recursion traverses through one node, so total is O(N1+N2) once again
    if list1.val <= list2.val:
        list1.next = mergeTwoListRecursive(list1.next, list2)
        return list1    else:
        list2.next = mergeTwoListRecursive(list1, list2.next)
        return list2def mergeTwoLists(list1, list2):
    head = ListNode()
    begin = head
    head.next = mergeTwoListRecursive(list1, list2)  # O(N1+N2)
    return begin.next

The time complexity is still O(N1+N2), same as the iterative solution.

To me, this problem seems more intuitive with the iterative approach, but YMMV. Since there’s no advantage choosing either one over the other, you should choose the one you feel more comfortable and more intuitive. Make sure to explain things well, then you should be good.

That’s it! Another problem down.

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz

The Blind 75 Leetcode Series: Merge Two Sorted Lists

Written by Jonathan Chao