JavaScript | Merge Two Sorted Linked List

Asked in Amazon, Google

Merge Two Linked List

Input:
arr1[] = [3, 9, 10, 18, 23],
arr2[] = [5, 12, 15, 20, 21, 25]
m = 5, n = 6
Output: [3, 5, 9, 10, 12, 15, 18, 20, 21, 23, 25]

Explanation: The resultant array i.e. arr1[] has all the elements of arr1[] and arr2[], sorted in increasing order. The size of resultant array is m + n = 5 + 6 = 11

Approach,

• We create an auxiliary array of size m+n
• While traversing through both the arrays: Pick the smaller of current elements of arr1 and arr2, save the smaller value of both the arrays in the auxiliary array, thereby increment the positions accordingly.
• Now copy the auxiliary array to arr1 as the final array should be arr1

// Definition for singly-linked list.
 function Node(val) {
      this.val = val;
      this.next = null;
  }
 
/**
 * @param {Node} list1
 * @param {Node} list2
 * @return {Node}
 */
var mergeTwoLists = function(list1, list2) {
    let finalList = new Node();
    let head = finalList;
    
    while (list1 !== null && list2 !== null) {
 
 // Select the smallest value from either linked list,
 // then increment that list forward.
        
       if (list1.val < list2.val) { 
           finalList.next = new Node(list1.val)    
           list1 = list1.next
        } else {
            finalList.next = new Node(list2.val)
            list2 = list2.next
        }
        
        finalList = finalList.next
    }
    
// It's possible that one linked list is shorter than the other, so we can just add the remainder of the last linked list.
    
    if (list1 !== null)
        finalList.next = list1
    if (list2 !== null)
        finalList.next = list2
    
// return .next because this first element in the linkedlist is empty
    return head.next
};

Follow me for more coding interview.

This problem is very popular in the coding interviews.

Keep learning, keep growing!

Don’t forget to follow me for more such articles, and subscribe to our newsletter.

Let’s connect on LinkedIn!. Please read more for more data structure javascript question.