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
list1
andlist2
are sorted in non-decreasing order.
Now, let’s see the code of 21. Merge Two Sorted Lists – Leetcode Solution.
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 = next def 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 = next def 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.