In this post, we are going to solve the 21. Merge Two Sorted Lists problem of Leetcode. This problem 21. Merge Two Sorted Lists is a Leetcode easy level problem. Let’s see the code, 21. Merge Two Sorted Lists – Leetcode Solution.
Problem
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.
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
list1andlist2are sorted in non-decreasing order.
Now, let’s see the code of 21. Merge Two Sorted Lists – Leetcode Solution.
21. Merge Two Sorted Lists – Solution in Java
This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in Java Programming Language.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new ListNode(0); ListNode handler = head; while(l1 != null && l2 != null) { if (l1.val <= l2.val) { handler.next = l1; l1 = l1.next; } else { handler.next = l2; l2 = l2.next; } handler = handler.next; } if (l1 != null) { handler.next = l1; } else if (l2 != null) { handler.next = l2; } return head.next; }}Now let’s see the Recursive approach to solve the same problem in Java using Recursion.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode handler; if(l1.val < l2.val) { handler = l1; handler.next = mergeTwoLists(l1.next, l2); } else { handler = l2; handler.next = mergeTwoLists(l1, l2.next); } return handler; }}21. Merge Two Sorted Lists – Solution in C++
This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in C++ Programming Language.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* temp = new ListNode(-1); ListNode* head = temp; while(l1!=NULL and l2!=NULL){ if(l1->val<=l2->val){ head->next = l1; l1 = l1->next; } else { head->next = l2; l2 = l2->next; } head=head->next; } if(l1!=NULL) { head->next = l1; } else head->next = l2; return temp->next; }};Now let’s see the Recursive approach to solve the same problem in C++ using Recursion.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(l1 == NULL) {return l2;}if(l2 == NULL) {return l1;} if(l1 -> val <= l2 -> val) {l1 -> next = mergeTwoLists(l1 -> next, l2);return l1;}else {l2 -> next = mergeTwoLists(l1, l2 -> next);return l2; }}};21. Merge Two Sorted Lists – Solution in Python
This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in Python Programming Language.
# Definition for singly-linked list.# class ListNode(object):# def __init__(self, val=0, next=None):# self.val = val# self.next = nextdef mergeTwoLists1(self, l1, l2): dummy = cur = ListNode(0) while l1 and l2: if l1.val < l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 or l2 return dummy.next
Now let’s see the Recursive approach to solve the same problem in Python using Recursion.
# Definition for singly-linked list.# class ListNode(object):# def __init__(self, val=0, next=None):# self.val = val# self.next = nextdef mergeTwoLists2(self, l1, l2): if not l1 or not l2: return l1 or l2 if l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2
Note: This problem 21. Merge Two Sorted Lists is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.
