# Merge k Sorted Lists

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

/**
* 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

/**
* 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

/**
* 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

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


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


Does deconstructing has such a negative impact on performance?