LeetCode 21 Solution: How to Merge Two Sorted Lists in Python

The LeetCode 21 solution involves merging two sorted linked lists, a common coding challenge you’ll often encounter in coding interviews and platforms like LeetCode. The LeetCode 21 problem, titled “Merge Two Sorted Lists”, offers an excellent opportunity to practice linked list operations and solve problems efficiently with minimal time complexity.

Problem Explanation

In the LeetCode 21 problem, you get the heads of two sorted linked lists. Your task is to merge these lists into one sorted list. You can’t create new nodes. Instead, you need to “splice” the nodes from the original lists. After merging, return the head of the new linked list.

For example:

• If list1 = [1,2,4] and list2 = [1,3,4], the merged result should be [1,1,2,3,4,4].

Let’s walk through how to solve this problem efficiently in Python.

Algorithm Approach for LeetCode 21 Solution

Since both input lists are already sorted, an effective way to merge them is by using a two-pointer technique. You compare the values of the nodes from both lists, choose the smaller node, and link it to the merged list. Then, move the pointer of the list from which you took the smaller node. Repeat this process until both lists are fully merged.

To simplify this, you can use a dummy node. The dummy node serves as a placeholder for the start of the merged list. It makes managing edge cases easier and helps build the list without extra conditions.

Python Code for Merging Two Sorted Lists

Here’s how you can implement the solution in Python:

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

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    # Create a dummy node to start the merged list
    dummy = ListNode()
    current = dummy

    # Traverse both lists and merge them
    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next

    # If one of the lists is not empty, append it to the result
    current.next = list1 if list1 else list2

    # Return the merged list, which starts after the dummy node
    return dummy.next

How the Solution Works

• Step 1: We initialize a dummy node. This helps avoid dealing with special cases for the head of the merged list.
• Step 2: A current pointer is used to track the end of the merged list as we add nodes from either list1 or list2.
• Step 3: We compare the current node of list1 and list2. Whichever node has the smaller value is linked to the current pointer, and then that list’s pointer is moved forward.
• Step 4: If one of the lists is exhausted (becomes None), we simply attach the remaining nodes from the other list to the merged list.
• Step 5: Finally, we return dummy.next, which points to the head of the merged list (the first node after the dummy).

Handling Edge Cases

This solution efficiently handles several edge cases:

• Both lists are empty: If list1 and list2 are both None, the merged list will also be empty, and the function will return None.
• One list is empty: If either list1 or list2 is empty, the function will simply return the non-empty list as the result.
• Lists with duplicates: The solution merges duplicate values correctly since we compare the values of the nodes in each step.

Time and Space Complexity

The time complexity of this solution is O(n + m), where n is the number of nodes in list1 and m is the number of nodes in list2. This is because we are traversing each list exactly once. The space complexity is O(1) (excluding the input and output lists), as we only use a few extra pointers to track the current nodes during the merge.

Why This Approach Works for LeetCode 21 Solution

This approach works because both lists are already sorted. By comparing the nodes and moving through both lists simultaneously, you build the merged list in sorted order without needing to sort it later.

The use of a dummy node simplifies the merging process, especially when the lists are uneven in length or one of them is empty. Since the linked lists are small, with a maximum of 50 nodes each, the linear time complexity of O(n + m) is sufficient to meet the problem’s performance requirements.

Conclusion

The LeetCode 21 problem is a great example of how understanding data structures, like linked lists, can lead to efficient solutions. Applying the right algorithm, such as the two-pointer technique, further enhances the approach. By using a dummy node to handle edge cases and merging the lists in linear time, you can solve the merge two sorted lists problem effectively.

This solution not only helps you ace coding interviews but also deepens your understanding of linked lists and algorithmic thinking. With Python, the implementation becomes straightforward and easy to follow, allowing you to tackle similar problems with confidence.

Happy Coding!

---

Looking for more LeetCode solutions? Stay tuned for upcoming guides on tackling other LeetCode challenges in Python. Whether you’re preparing for technical interviews or aiming to improve your coding skills, exploring a variety of problems will enhance your understanding and proficiency.

You can find this problem on LeedCode, click here.