Leetcode #06: ‘Merge Two Sorted Lists’

Linked lists are an essential data structure in computer science that is used to store and manipulate collections of data. They are instrumental when the collection size is not known in advance, or when dynamic memory allocation is required.

In this article, we will explore a solution to the Leetcode problem of merging two sorted linked lists in Python. We will explain the problem statement, provide an algorithmic solution, and include Python code with comments.

Problem Statement:

Given the heads of two sorted linked lists, merge the two lists into a single sorted list. The resulting list should be made by splicing together the nodes of the first two lists.

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

Solution:

To solve this problem, we can create a new linked list and iterate over the two input lists, comparing the values of their nodes and adding the smaller node to the new list. We can use two pointers to keep track of the current nodes in the input lists, and a third pointer to keep track of the current node in the new list.

We can start by creating a new dummy node that will be the starting node of the merged list. We can then iterate over the two input lists using a while loop that continues until one of the input lists is exhausted.

Inside the while loop, we can compare the values of the current nodes in the input lists. If the value of the node in the first list is smaller, we can add it to the new list and move the pointer to the next node in the first list. If the value of the node in the second list is smaller, we can add it to the new list and move the pointer to the next node in the second list.

Once the while loop has been completed, we can check if there are any remaining nodes in either of the input lists. If there are, we can simply add them to the end of the new list.

Finally, we can return the starting node of the new list, which is the next node after the dummy node.

class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Create a dummy node and a reference to it for the current node
        dummy = cur = ListNode(0)
        
        # Continue the loop while both lists are not empty
        while l1 and l2:
            # Check which value is smaller between the two lists
            if l1.val < l2.val:
                # If the value from l1 is smaller, add it to the current node and move l1 to the next node
                cur.next = l1
                l1, cur = l1.next, cur.next
            else:
                # If the value from l2 is smaller, add it to the current node and move l2 to the next node
                cur.next = l2
                l2, cur = l2.next, cur.next
                
        # If either of the lists still has nodes, add them to the end of the merged list
        if l1:
            cur.next = l1
        if l2:
            cur.next = l2
            
        # Return the merged list, starting from the first node after the dummy node
        return dummy.next

Merge two Sorted Lists

Time Complexity:

The time complexity of this algorithm is O(m+n), where m and n are the lengths of the input lists. This is because we need to iterate over both input lists once in order to create the merged list.

Space Complexity:

The space complexity of this algorithm is O(1), because we only need to create a new dummy node and use a constant amount of additional memory to merge the input lists.

Conclusion:

In this article, we have explored a solution to the problem of merging two sorted linked lists. By creating a new linked list and iterating over the input lists, we can create a single sorted list in O(m+n) time and O(1) space. This solution is simple, efficient and can be applied to a variety of linked list problems