# Merge Two Sorted Lists – Leetcode Solution

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` and `list2` 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.