JavaScript | Merge Two Sorted Linked List

Merge Two Linked List

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sonika | Working at Walmart | startlearncoding.com

Sonika | Working at Walmart | startlearncoding.com

Working in Walmart as Senior UI Developer | React | JavaScript | Data Structure