Merge Two Sorted Lists (Leet code-21)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 21. This is a Leet code problem named Merge Two Sorted Lists. We will solve it using python and it is the best space and time-optimized solution.

Question of Merge Two Sorted Lists

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.

Create a function that combines two lists that are individually sorted in increasing order into a single list that is also sorted in increasing order. Return the new list from the function. The nodes of the first two lists should be combined to create the new list.

There are other scenarios to consider: either ‘a’ or ‘b’ may be empty; during processing, either ‘a’ or ‘b’ may run out first; and lastly, there is the issue of the result list starting out empty and growing as you move through ‘a’ and ‘b.

Example

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.

Approach to solve Merge Two Sorted Lists

We will solve it using a dummy node.

The method in use here starts the result list with a temporary fake node. Appending additional nodes is simple since the pointer Tail always links to the final node in the result list.

When the result list is empty, the fake node offers the tail a starting place. Since it is just temporary and is allocated on the stack, this fake node is effective. As it continues, the loop adds a new node to the tail while eliminating one node from either ‘a’ or ‘b’. When

Algorithm

This method performs the following steps for a given input array:

check base condition
Check the smallest number in both list and point new head to that list
we store the node in last node to track the last added node
run while loop till either of the list ends
now we compare the value of list1 and list2 and assign small value to new head
End While
if list1 ends then point last node to list 2
if list2 ends then point last node to list 1
return new_head

Python Code for Merge Two Sorted Lists

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        
        #check base condition
        if(list1==None):
            return list2
        if(list2==None):
            return list1    
        
        #Check the smallest number in both list and point new head to that list
        if(list1.val>list2.val):
            new_head = list2
            list2 = list2.next            
        else:
            new_head = list1
            list1=list1.next
            
        #we store the node in last node to track the last added node 
        last_node = new_head
            
        #run while loop till either of the list ends 
        while(list1!=None and list2!=None):
            #now we compare the value of list1 and list2 and assign small value to new head 
            if(list1.val>list2.val):
                last_node.next = list2
                last_node = list2
                list2 = list2.next

            else:
                last_node.next = list1
                last_node = list1
                list1 = list1.next
            

        #if list1 ends then point last node to list 2
        if(list1 ==None):
            last_node.next = list2
        
        #if list2 ends then point last node to list 1
        if(list2==None):
            last_node.next = list1
            
                
        #return new_head
        return new_head