1
\$\begingroup\$

The task is taken from LeetCode

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

I'm struggling with the solution as none of them seem to be very fast:

My solution 1

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (!lists || !lists.length) { return null; }
  let pointer;
  let firstElement = null;
  while (!lists.every(x => x === null)) {
    let min;
    let iMin;
    for (let i = 0; i < lists.length; i++) {
      if (lists[i] && (min === void 0 || min > lists[i].val)) {
        min = lists[i].val;
        iMin = i;
      }
    }
    if (!firstElement) {
      firstElement = lists[iMin];
    } else {
      pointer.next = lists[iMin];        
    }
    pointer = lists[iMin];
    if (!lists[iMin].next) {
       lists.splice(iMin,1);        
    } else {
       lists[iMin] = lists[iMin].next;    
    }        
  }
  return firstElement;
};

Runtime O(k n)

My solution 2

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (!lists || !lists.length) { return null; }
  const mergeLists = (l1, l2) => {
    if (!l1 || !l2) { return l1 ? l1 : l2; }
    let first = null;
    let pointer = null;
    while(l1 || l2) {
      let current;
      if (!l1 || !l2) {
        current = l1 ? l1 : l2;

        if (!first) { return current; }

        pointer.next = current;
        return first;
      }

      if (l1.val < l2.val) {
        current = l1;
        l1 = l1.next;
      } else {
        current = l2;
        l2 = l2.next;
      }        

      if (first) {
        pointer.next = current;
      } else {
        first = current;
      }
      pointer = current;
    }
    return first;
  }

  return lists.reduce((ac, l) => mergeLists(ac, l));

};

Runtime O(n log k)

with k the number of lists elements.

EDIT:

Not really my solution because I read them up and then played around with it:

My solution 3

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (!lists || !lists.length) { return null; }
  const mergeLists = (l1, l2) => {
    if (!l1) { return l2; }
    if (!l2) { return l1; }
    if (l1.val < l2.val) {
      l1.next = mergeLists(l1.next, l2);
      return l1;
    } else {
      l2.next = mergeLists(l2.next, l1);
      return l2;
    }
  }

  return lists.reduce((ac, l) => mergeLists(ac, l));

};

My solution 4

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (!lists || !lists.length) { return null; }
  const mergeLists = (l1, l2) => {
    if (!l1) { return l2; }
    if (!l2) { return l1; }
    if (l1.val < l2.val) {
      l1.next = mergeLists(l1.next, l2);
      return l1;
    } else {
      l2.next = mergeLists(l2.next, l1);
      return l2;
    }
  }
  let i = lists.length;
  while(i-- >= 2) {
    const l1 = lists.shift();
    const l2 = lists.shift();
    lists.push(mergeLists(l1,l2));
  }
  return lists[0];
};

The solution 3 is just as slow as the other first two. But solution 4 is nearly 3 times as fast, eventhough I just replaced the while loop with the reduce function (reduce is at the end of the day also a loop; but how come the difference is that big?)

Also when I applied the following ecmascript6 syntax to solution 4 it would then be even slower than the other solutions:

var mergeKLists = function(lists) {
  if (!lists || !lists.length) { return null; }
  const mergeLists = (l1, l2) => {
    if (!l1) { return l2; }
    if (!l2) { return l1; }
    if (l1.val < l2.val) {
      l1.next = mergeLists(l1.next, l2);
      return l1;
    } else {
      l2.next = mergeLists(l2.next, l1);
      return l2;
    }
  }
  let i = lists.length;
  while(i-- >= 2) {
    // const l1 = lists.shift();
    // const l2 = lists.shift();

    // start making changes
    const [l1, l2, ...rest] = lists;
    lists = rest;
    // end making changes
    lists.push(mergeLists(l1,l2));
  }
  return lists[0];
};

Does deconstructing has such a negative impact on performance?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.