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}…