2017-10-22 @sunderls

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.

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 * k^{2}).

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?

- 1st round: k/2 groups, each cost
`O(m * 2)`

,`O(m * 2 * k / 2) = O(m * k)`

- 2nd round: k/4 groups, each cost
`O(2m * 2)`

,`O(m * 4 * k / 4) = O(m * k)`

- ..
- lg(k) round

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

complexity.

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

```
/**
* Definition for singly-linked list.
* 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;
}
return head.next;
};
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[0];
};
```

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

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

- 1st round:
`O(m * 2)`

, now k - 1 lists left - 2nd round:
`O(m * 3)`

, now k - 2 lists left - ..
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 .

sorry I've already forgot after graduation.

如果觉得有帮助到你的话，

欢迎支付宝donate