Merge Two Sorted Lists Leetcode Solution
Merge Two Sorted List LeetCode Solution :
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into 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.
Merge Two Sorted Lists LeetCode Solution :
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 for Merge Two Sorted Lists LeetCode Solution : :
We start by initializing a dummy node. This dummy node is a placeholder and simplifies the code since it allows us to handle the edge cases more easily.
We have two pointers, one for each input linked list (list1 and list2), initially pointing to their respective heads.
We iterate through both lists, comparing the values of the nodes pointed to by the two pointers.
At each step, we append the node with the smaller value to the merged list, and we advance the corresponding pointer to the next node in that list.
We repeat this process until we have iterated through both lists entirely.
If one of the lists becomes exhausted before the other, we simply attach the remaining part of the non-empty list to the merged list.
Finally, we return the head of the merged list, which is the next node after the dummy node.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code for Merge Two Sorted Lists LeetCode Solution : :
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
// if list1 happen to be NULL
// we will simply return list2.
if(list1 == NULL)
return list2;
// if list2 happen to be NULL
// we will simply return list1.
if(list2 == NULL)
return list1;
ListNode * ptr = list1;
if(list1 -> val > list2 -> val)
{
ptr = list2;
list2 = list2 -> next;
}
else
{
list1 = list1 -> next;
}
ListNode *curr = ptr;
// till one of the list doesn't reaches NULL
while(list1 && list2)
{
if(list1 -> val < list2 -> val){
curr->next = list1;
list1 = list1 -> next;
}
else{
curr->next = list2;
list2 = list2 -> next;
}
curr = curr -> next;
}
// adding remaining elements of bigger list.
if(!list1)
curr -> next = list2;
else
curr -> next = list1;
return ptr;
}
};class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head = new ListNode(0);
if(list1 == null && list2 == null) return null; //null checking
if(list1 == null) return list2;
if(list2 == null) return list1;
if(list1.val > list2.val) { //comparing and merging
head = list2;
list2 = list2.next;
}
else {
head = list1;
list1 = list1.next;
}
head.next = mergeTwoLists(list1, list2);
return head;
}
}
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head = sort_list = ListNode(0)
while(l1 and l2):
if (l1.val < l2.val):
sort_list.next = l1
l1 = l1.next
sort_list = sort_list.next
elif (l1.val >= l2.val):
sort_list.next = l2
l2 = l2.next
sort_list = sort_list.next
sort_list.next = l1 or l2
return head.next
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment