Merge Two Sorted Lists Solution Amazon OA 2022

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: Merge Two Sorted Lists Solution in C++

``````/**
* 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;
{
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: Merge Two Sorted Lists Solution in Java

``````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;
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: Merge Two Sorted Lists Solution in 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