Categories
interview

Merge Two Sorted Lists

/**
* Definition for singly-linked list.
* function ListNode(val, next) {
*   this.val = (val===undefined ? 0 : val)
*   this.next = (next===undefined ? null : next)
* }
* / 
/*
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/

var mergeTwoLists = function(a, b) {
  if(a === null)
    return b;
  if(b === null)
    return a;
  let result = a;
  if(a.val <= b.val) {
    result.next = mergeTwoLists(a.next, b);
  } else {
    result = b;
    result.next = mergeTwoLists(a, b.next);
  }
  return result;
};

/// START TEST DATA ///
var a = {
  val: 1,
  next: {
         val: 2,
         next: {
                 val: 4,
                 next: null
                }
        }
      };

var b = {
         val: 1,
         next: {
                val: 3,
                next: {
                       val: 4,
                       next: null
                       }
                  }
          };
/// END TEST DATA ///

var answer = mergeTwoLists(a, b);
while (answer !== null) {
  console.log(answer.val);
  answer = answer.next;
}

// Output: 1 , 1, 2, 3, 4, 4

Demo