21. Merge Two Sorted Lists — LeetCode(Python)

I got you!

Problem:

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.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Solution:

1. Iterative Method —

dummy = curr = ListNode()
        
while list1 and list2:
    if list1.val < list2.val:
        curr.next = list1
        list1 = list1.next
    else:
        curr.next = list2
        list2 = list2.next
    curr = curr.next
            
curr.next = list1 or list2
            
return dummy.next

Explanation —

We start by creating a dummy node that will come in handy while returning the merged list.

Now, we simply traverse both the lists until either one or both are exhausted.

If the current value of the list1 node is smaller than the value of the current list2 node, we append the list1 node to our curr’s next pointer, and move to the next node in list1.

Similarly, we append the list2 node to our curr’s next pointer, and move to the next node in list2, if the value in list2 is smaller.

After this, we also move the curr node to it’s next node.

The while loop CAN terminate if both the lists are exhausted. But what if the two lists were not of equal length?

We then point the next pointer of our curr node to the remaining list, because we know that it is already sorted.

Finally, we return the next node to our dummy node which is where our new merged list starts from.

Time and Space Complexity —

Since we are traversing through the lists only once, we can say that our code requires linear amount of time to run.

Also, we are using a constant amount of extra space.

Thus, if m is the length of list1 and n is the length of list2,

Time Complexity: O(m+n)

Space Complexity: O(1)

2. Recursive Method —

if not list1 or not list2:
    return list1 or list2
        
if list1.val < list2.val:
    list1.next = self.mergeTwoLists(list1.next, list2)
    return list1
else:
    list2.next = self.mergeTwoLists(list1, list2.next)
    return list2

Explanation —

The termination condition of our recursion is when either of the lists has been exhausted; in which case, we return the remaining list.

If the value of the current node in list1 is smaller than that of list2, we call the function recursively on the remainder of list1 and the entire list2 — and we append this answer to our current list1 node.

Otherwise, we call the function recursively on list1 and the remainder of list2 — and we append this answer to our current list2 node.

In both cases, we return the node containing the smaller number.

Time and Space Complexity —

Since we are traversing through the lists only once, we can say that our code requires linear amount of time to run.

Also, since the recursion stack stores all elements in both the lists at some point, we need a linear amount of extra space.

Thus, if m is the length of list1 and n is the length of list2,

Time Complexity: O(m+n)

Space Complexity: O(m+n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏