Leetcode – Merge Two Sorted Lists Solution in Python

Spread the love

Merge Two Sorted Lists is a common problem on LeetCode that tests your knowledge of linked lists and algorithmic thinking. This problem is classified as easy, but the simplicity of its statement can be deceiving. However, by breaking down the problem and applying the right data structures and algorithms, this problem becomes much more manageable.

In this article, we’ll discuss how to approach and solve the Merge Two Sorted Lists problem step-by-step.

Understanding the Problem

The problem statement is as follows:

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Here, we’re given two singly linked lists, and both of them are sorted in non-decreasing order. The task is to merge these two linked lists into one, such that the resulting linked list is also sorted.

The problem assumes basic familiarity with linked list data structures. If you’re new to linked lists, here’s a quick recap: a linked list is a linear data structure where each element is a separate object, each comprising a node that holds data and a reference (link) to the next node in the sequence.

Python Linked List Implementation

In Python, we don’t have built-in linked list support, so we’ll need to define a class to represent a Node in the linked list. Each Node has a value and a next pointer which points to the next Node in the list.

Here’s a simple Python implementation:

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

Approach to Solving the Problem

To solve this problem, we need to iterate through both linked lists. At each step, we’ll compare the values of the current nodes in both lists. The node with the smaller value is added to the result list and move its pointer to the next node. We continue this process until we reach the end of either list. If there are remaining elements in either of the lists, we add those to the end of the result list.

Python Solution for Merge Two Sorted Lists

Now, let’s translate our approach into Python code:

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # create a dummy node
        dummy = ListNode(0)
        # tail represents the last result node
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            
            # move the tail
            tail = tail.next
        
        # append the rest of the list, if any
        if l1:
            tail.next = l1
        elif l2:
            tail.next = l2

        return dummy.next

This function starts by initializing a dummy node, and a tail pointer that points to the last node in the result list. Then it enters a loop that continues until we reach the end of either l1 or l2. In each iteration of the loop, it compares the value of the nodes pointed to by l1 and l2, and appends the smaller node to the result list.

When we exit the loop, it means we’ve reached the end of one of the lists. If there are any remaining nodes in either list, we append those to the result list. Since the input lists are sorted, the remaining nodes will also be in sorted order.

Finally, the function returns dummy.next, which is the head of the merged list.

This solution works in O(n) time complexity, where n is the total number of nodes in both lists. The space complexity is O(1), as we only use a constant amount of extra space.

In conclusion, solving the Merge Two Sorted Lists problem on LeetCode requires understanding linked lists and how to manipulate them. By creating a dummy node and iterating through both lists, we can create a new linked list that contains all elements in sorted order. This problem is a good practice for anyone learning about linked lists and algorithmic problem solving in Python.

Leave a Reply