# Merge Two Sorted Lists Solution Amazon OA 2021

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.

Also See: Amazon OA Online Assessment 2021 Questions and Answers

## 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 = `

Output: ``

## 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 C++

```/**
* 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:

//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
{
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;
}

}
};```

Program Java

```class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l2 == null) return l1;
if (l1 == null) return l2;

// ensure l1 < l2 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;
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 Python

```# 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):
newTail = l1
l1 = l1.next
newTail.next = l2
else:
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