Merge Two Sorted Lists - Company-specific OAs / Amazon OA

Problems
1

https://algo.monster/problems/merge_two_sorted_lists

2

Dude where’s the javascript for these problems

3

agree with needing more js solutions on this site

4

Solution using Min Heap:

public static Node<Integer> merge(Node<Integer> l1, Node<Integer> l2) {
        PriorityQueue<Node<Integer>> pq = new PriorityQueue<>((a, b) -> {
            return a.val.compareTo(b.val);
        });
        
        if (l1 != null)
            pq.add(l1);
        if (l2 != null)
            pq.add(l2);
         
        Node head = null;
        Node tail = null;
        
        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            
            if(head == null) {
                head = curr;
                tail = head;
            } else {
                tail.next = curr;
                tail = tail.next;
            }
            
            if (curr.next != null) {
                pq.add(curr.next);
            }
        }
        
        return head;
    }
5

It’s useful while merging k sorted lists. Simple loop gives better time complexity for two lists.

6 

// Iterative version.

const merge = (l1, l2) => {
    
     let dummy = new Node(-1);
     const result = dummy;
     let current_1 = l1;
     let current_2 = l2;

     while (current_1 && current_2) {
           if (current_1.val < current_2.val) {
                    dummy.next = current_1;
                    current_1 = current_1.next;
           } else {
                    dummy.next = current_2;
                    current_2 = current_2.next;
          }

          dummy = dummy.next;
     }

     // if still one of the list has elements.
    if (current_1)  dummy.next  = current_1;
    if (current_2)  dummy.next  = current_2 ;
    
    return result.next
}

For the recursive version.


const merge = (l1, l2) => {
  
    if (l1 === null && l2 === null) return null;
    if (l1 === null) return l2
    if (l2 === null) return l1
   
   if (l1.val < l2.val) {
       const next = l1.next
       l1.next = merge(next, l2)
      return l1
   } else {
       const next = l2.next
       l2.next = merge(l1, next)
       return l2
   } 

}