Merge Two Sorted Lists Leetcode Problem 21 [Python Solution]

Whether new or just getting with programming, data structures and algorithms, LeetCode problems which today today is Merge Two Sorted Lists, etc, are key pillars to skill development.

If you’re new to programming or just getting started with data structures and algorithms, solving LeetCode problems can be a great way to practice and learn.

In this blog post, we’ll walk you through the solution to the Merge Two Sorted Lists problem, which is categorized as an easy problem on LeetCode.

This problem falls under the category of linked lists and is often used as a fundamental exercise.

Problem Overview

You are given two sorted linked lists, list1 and list2.

Your task is to merge these two lists into a single sorted list.

The merged list should be created by splicing together the nodes from the first two lists.

Finally, return the head of the merged linked list.

Example:

Let’s look at an example to understand the problem better:

Input:

list1 = [1,2,4]

list2 = [1,3,4]

Output:

[1,1,2,3,4,4]

In this example, we merge the two sorted lists list1 and list2 to get the merged list [1,1,2,3,4,4].

Constraints

Before we dive into the solution, it’s essential to understand the constraints of the problem.

These constraints define the boundaries within which our solution must operate:

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

Now that we have a clear understanding of the problem, let’s explore the solution.

Efficient Python Code Solution

We will provide an efficient Python solution for this problem.

We’ll cover both an iterative and a recursive approach.

Iterative Approach

In the iterative approach, we use a dummy node to handle the edge case of an empty list.

Then, we compare the values of the nodes in both lists, and we merge them in a sorted manner.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
    dummy = node = ListNode()

    while list1 and list2:
        if list1.val < list2.val:
            node.next = list1
            list1 = list1.next
        else:
            node.next = list2
            list2 = list2.next
        node = node.next

    node.next = list1 or list2

    return dummy.next

In this code, we create a dummy node to handle the case of an empty list.

We then use a node pointer to iterate through the lists.

As long as both list1 and list2 are not empty, we compare the values of the current nodes in both lists.

We insert the smaller value into our result list, and then move the pointer in the respective list forward.

Finally, when one of the lists becomes empty, we append the remaining portion of the other list to our result.

The dummy.next is the head of our merged sorted list, so we return it.

Recursive Approach

We can also solve this problem using a recursive approach.

Here’s the Python code for it:

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    if not list1:
        return list2
    if not list2:
        return list1
    lil, big = (list1, list2) if list1.val < list2.val else (list2, list1)
    lil.next = self.mergeTwoLists(lil.next, big)
    return lil

In the recursive solution, we check if either of the input lists is empty.

If one of them is empty, we return the other list because it’s already sorted.

Next, we determine which list’s current node has a smaller value, and we make that list the “lil” (short for little) list and the other list the “big” list.

We update the lil.next to be the result of the recursive call with lil.next and big as the arguments.

This approach continues recursively until one of the lists becomes empty, and we merge the remaining portion of the other list.

Now that we’ve provided efficient Python solutions to this problem, let’s discuss the time and space complexity of these solutions.

Time and Space Complexity

Understanding the time and space complexity of your code is crucial when working with data structures and algorithms.

Let’s analyze the complexities of our solutions.

Iterative Approach

• Time Complexity: O(N)
• In the worst case, we have to traverse all the nodes in both lists, where N is the total number of nodes.
• Space Complexity: O(1)
• We use a constant amount of extra space.

Recursive Approach

• Time Complexity: O(N)
• Similar to the iterative approach, in the worst case, we have to traverse all the nodes in both lists.
• Space Complexity: O(N)
• The space complexity for the recursive call stack is O(N) in the worst case.

Both approaches have a time complexity of O(N), which is optimal given that we must examine all the nodes.

However, the recursive approach has a slightly higher space complexity due to the recursive call stack.

Reasoning Behind Our Approach

Our approach to this problem is based on the principle of merging two sorted lists while maintaining their order.

We use a dummy node to handle edge cases, ensuring that our result list is never empty.

In the iterative approach, we compare values and merge the lists step by step, making it easy to understand and implement.

The recursive approach, on the other hand, elegantly divides the problem into smaller subproblems.

By understanding both iterative and recursive approaches, you’ll gain insights into different problem-solving strategies and coding techniques.

Related Interview Questions By Company:

• Next Greater Element I LeetCode
• Merge Two Binary Trees LeetCode
• Minimum Difference Between Highest And Lowest Of K Scores LeetCode

Related Interview Questions By Difficulty:

• Partition List LeetCode
• Maximum Twin Sum Of A Linked List LeetCode
• Linked List Cycle LeetCode

Related Interview Questions By Category:

• Maximum Sum Circular Subarray LeetCode
• Multiply Strings LeetCode
• Guess Number Higher Or Lower LeetCode

Conclusion

In this blog post, we’ve walked you through the solution to the Merge Two Sorted Lists problem on LeetCode.

We’ve covered both an iterative and a recursive approach, explaining the reasoning behind each.

We’ve also discussed the time and space complexity of our solutions.

If you’re a beginner, it’s essential to practice solving such problems to enhance your problem-solving skills and algorithmic thinking.

The key takeaways from this problem include handling edge cases, comparing values, and merging lists while maintaining their sorted order.

Feel free to leave a comment, ask questions, make suggestions, or share your thoughts on this problem.

Your feedback and engagement are valuable in the learning process.

You can find the original problem on LeetCode at Merge Two Sorted Lists.

Keep practicing, and happy coding!