Merge Two Sorted Lists Amazon OA 2023

Merge Two Sorted Lists Amazon OA 2023 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.
Merge Two Sorted Lists Amazon Online Assessment
Merge Two Sorted Lists Amazon Online Assessment

SOLUTION

Program: Merge Two Sorted Lists Amazon OA Solution in 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:
    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: Merge Two Sorted Lists Amazon OA 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;
            // 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: Merge Two Sorted Lists Amazon OA 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):
            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

Amazon OA 2023 Questions with Solution

  1. Shopping Patterns Solution Amazon OA 2023
  2. Reorder Data in Log Files Solution Amazon OA 2023
  3. Top K Frequent Words Solution Amazon OA 2023
  4. Trees Height Solution Amazon OA SDE 2023
  5. Counting Binary Substrings Amazon OA 2023
  6. Grid Connections Amazon OA 2023
  7. Shipment Imbalance Amazon OA 2023
  8. Max Profit Amazon OA 2023
  9. Find Lowest Price Amazon OA 2023
  10. Decode String Frequency Amazon OA 2023
  11. Simple Cipher Amazon OA 2023
  12. Valid Discount Coupons Amazon OA 2023 Solution
  13. Count Maximum Teams Amazon OA 2023
  14. Minimum Coin Flips Amazon OA 2023
  15. Max Average Stock Price Amazon OA 2023 Solution
  16. Robot Bounded In Circle Amazon OA 2023
  17. Shopping Options Amazon OA 2023 Solution
  18. Fill The Truck Maximum Units on a Truck Amazon OA Solution
  19. Maximize Score After N Operations Number Game Solution Amazon OA 2023
  20. Slowest Key Amazon OA 2023 Solution
  21. Five Star Seller Maximum Average Pass Ratio Amazon OA 2023
  22. Split String Into Unique Primes Amazon OA 2023 Solution
  23. Storage Optimization Amazon OA 2023 Solution
  24. Minimum Difficulty of a Job Schedule Amazon OA 2023 Solution
  25. Autoscale Policy Utilization Check Amazon OA 2023
  26. Optimal Utilization Solution Amazon OA 2023
  27. Two Sum Unique Pairs Solution Amazon OA 2023
  28. Amazon Music Pairs Amazon OA 2023 Solution
  29. Class Grouping Amazon OA 2023 Solution
  30. Find Max products Amazon OA 2023 Solution
  31. Get encrypted number Amazon OA 2023 Solution
  32. Find Total Imbalance Amazon OA 2023 Solution
  33. Find Total Power Amazon OA 2023 Solution