Merge Two Sorted Lists Amazon OA 2023

Contents

1 Merge Two Sorted Lists Amazon OA 2023 Solution
- 1.1 SOLUTION
2 Amazon OA 2023 Questions with Solution

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

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

Merge Two Sorted Lists Amazon OA 2023 Solution

SOLUTION

Amazon OA 2023 Questions with Solution