Page Contents

**Merge Two Sorted Lists Solution**

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the given two lists.

**Examples:**

**Example1:**

Input: l1 = [1,2,4], l2 = [1,3,4]

Output: [1, 1, 2, 3, 4, 4]

**Example 2:**

Input: l1 = [], l2 = []

Output: []

**Example 3:**

Input: l1 = [], l2 = [0]

Output: [0]

**Constraints:**

The number of nodes in both lists is in the range [0, 50].

- -100 <= Node.val <= 100
- Both l1 and l2 are sorted in non-decreasing order.

**SOLUTION**

** Program**:

**in C++**

*Merge Two Sorted Lists Solution*```
/**
* 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 *head_merge=0,*tail_merge=0;// head and tail for new linked_list
//push function to push nodes
void push(int key)
{
ListNode *temp=new ListNode;
temp->val=key;
temp->next=0;
if(head_merge==0)//if no nodes are there
{
head_merge=temp;
tail_merge=temp;
}
else
{
tail_merge->next=temp;
tail_merge=temp;
}
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//while one of the linked list ends
while(l1!=0 && l2!=0)
{
if(l1->val<=l2->val)
{
push(l1->val);
l1=l1->next;
}
else
{
push(l2->val);
l2=l2->next;
}
}
//if nodes are remaining in L1
while(l1!=0)
{
push(l1->val);
l1=l1->next;
}
//if nodes are remaining in L2
while(l2!=0)
{
push(l2->val);
l2=l2->next;
}
return head_merge;//head of newly creadted linked_list
}
};
```

** Program**:

**in Java**

*Merge Two Sorted Lists Solution*```
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l2 == null) return l1;
if (l1 == null) return l2;
// ensure l1[0] < l2[0] so we have the begining of the sorted list
if (l2.val < l1.val) {
ListNode swp = l2;
l2=l1;
l1=swp;
}
// l1 is now our inplace target, and we will pull from l2
// we will keep a pointer into l1 that is the last sorted element
// so we start this at the head of l1
ListNode t = l1;
while (t.next != null && l2 != null) { // while not end of list 1 or list 2
// skip over values less than next l2
while (t.next != null && t.next.val < l2.val) {
t = t.next;
}
// take the head of l2
ListNode insert = l2;
// advance l2
l2 = l2.next;
if (t != null) {
// insert the head of l2
ListNode tmp = t.next;
t.next = insert;
t.next.next = tmp;
}
}
if (t.next == null) { // we know here at least one list is empty, so if there's no more in l1, l2 may have some
t.next = l2; // just take rest of l2, (which might also be empty)
}
return l1;
}
}
```

** Program**:

**in Python**

*Merge Two Sorted Lists Solution*```
# 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, l1: ListNode, l2: ListNode) -> ListNode:
#if both of the nodes are empty just return the first empty node
if not l1 and not l2:
return l1
#if only the first node is empty return the second node
if not l1:
return l2
#if only the second node is empty return the first node
if not l2:
return l1
#save the head which is equal to the smaller of the beginning nodes
#also set the tail of the merged linked list
if(l1.val <= l2.val):
head = l1
newTail = l1
l1 = l1.next
newTail.next = l2
else:
head = l2
newTail = l2
l2 = l2.next
newTail.next = l1
#while both linked lists have nodes left
while(l1 and l2):
#attach newTail to the next smallest node
#and advance the respective l1 or l2 pointer
if(l1.val <= l2.val):
newTail.next = l1
l1 = l1.next
else:
newTail.next = l2
l2 = l2.next
#the next smallest node becomes the new tail
newTail = newTail.next
#if there's any nodes left in one of the two linked lists
#simply attach the tail to what's left
if(l1):
newTail.next = l1
elif(l2):
newTail.next = l2
return head
```