all articles

leetcode war 23 - Merge k Sorted Lists

2017-10-22

https://leetcode.com/problems/merge-k-sorted-lists/description/

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

analysis

we've done a k=2 case at our last article - leetcode war 21 - Merge Two Sorted Lists, it cost a O(m * 2) because each comparison of the heads of the lists generate a node in the final list.

so for k sorted list, if we do it in a same fasion, it would cost us `O(m * k) * k`, right? Every round we get the smallest number from k heads, which is O(k), and there art m k rounds, so O(m k2).

is there a better way ? comparing k elements every time seems very not performant. what if we do it in groups of two ? and merge them seperately?

1. 1st round: k/2 groups, each cost `O(m * 2)`, `O(m * 2 * k / 2) = O(m * k)`
2. 2nd round: k/4 groups, each cost `O(2m * 2)`, `O(m * 4 * k / 4) = O(m * k)`
3. ..
4. lg(k) round

so we can do it better with `O(m * k * lg(k))` complexity.

trial

we put in our solution method mergeTwoLists, and use a while loop to do this.

``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
var mergeTwoLists = function(l1, l2) {
var p1 = l1;
var p2 = l2;
var head = p3 = new ListNode();

while (p1 && p2) {
if (p1.val <= p2.val) {
p3.next = p1;
p1 = p1.next;
} else {
p3.next = p2;
p2 = p2.next;
}

p3 = p3.next;
}

if (p1) {
p3.next = p1;
}

if (p2) {
p3.next = p2;
}

};

var mergeKLists = function(lists) {
if (lists.length === 0) return null;
// if there are more than one list
// shift them out, merge them, and push them back
while(lists.length > 1) {
var a = lists.shift();
var b = lists.shift();
lists.push(mergeTwoLists(a, b));
}
return lists;
};``````

it passed! and ranking top 10% fast submissions, 168 ms. wow.

can we do better?

what if we do it one by one, rather than in groups, like

1. 1st round: `O(m * 2)`, now k - 1 lists left
2. 2nd round: `O(m * 3)`, now k - 2 lists left
3. .. n. nth round: `O(m * (n + 1))`, now k - n lists left k. (k - 1)th round: `O(m * k))`, now 1 lists left

so complexity is: `m * 2 + m * 3 + m * k = m * k(k + 1)/ 2 = O(m * k * k)`

not better than our grouping method.

while there is a solution page on leetcode, and our method is the fastest way, called Divide And Conquer . 