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
andlist2
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
Complexity Analysis
Time Complexity: O(n + m)
Space Complexity: O(1)
So here is the end of the post. If you find any issues or any questions then write a comment. Share with your friends.
Related Posts:
- Find Pivot Index (Leet Code-724)
- Spiral Matrix Problem Solution
- Isomorphic Strings
- Two Sum IV - Input is a BST (Leet Code-653)
- Search in a Binary Search Tree (Leet Code-700)
- Invert Binary Tree (Leet Code-266)
- Symmetric Tree (Leet Code-101)
- Maximum Depth of Binary Tree (Leet Code-104)
- Binary Tree Postorder Traversal (Leet Code-145)
- Binary Tree Inorder Traversal (Leet Code - 94)
- Binary Tree Pre-Order Traversal
- Binary Tree Level Order Traversal (Leet Code-102)
- Valid Parentheses (Leet Code-20)
- Remove Duplicates from Sorted List (Leet Code-83)
- Reverse Linked List (Leet code -206)
- Remove Linked List Elements (Leet Code-203)
- Ransom Note (Leet code-383)
- First Unique Character in a String (Leet code-387)
- Valid Sudoku (Leet Code-36)
- Search a 2D Matrix (Leet Code-74)
- Linked List Cycle (Leet Code-141)
- Pascal's Triangle (Leet Code - 118)
- Reshape the Matrix (Leet Code-566)
- Best Time to Buy and Sell Stock (Leet code-121)
- The Intersection of Two Arrays II (Leet Code)
- Binary Search - Leet Code
- Two Sum - Leet Code